•byndrsn
Client obisnuit
Karma: 19
Deconectat
Mesaje: 72
|
|
« Răspunde #6 : Mai 23, 2008, 22:52:23 » |
|
Daca K este par (si >= 4), lucrurile sunt mai simple. Cand K este >= 4, poti sa pui in barca un numar egal de oameni si canibali: succesorii nodului (i, i, 0) sunt (i - a, i - a, 1), unde a = 1, 2, ..., min(K / 2, i); succesorii nodului (i, i, 1) sunt (i + a, i + a, 0), unde a = 1, 2, .., min(K / 2, N - i).
Din fiecare nod (i, i, 0) poti alege sa trimiti greedy cat mai multi oameni/canibali (maximizezi a). Din fiecare nod (i, i, 1) poti alege sa trimiti inapoi cat mai putini oameni/canibali (minimizezi a). Pentru N = 12, K = 4, primii pasi sunt cam asa:
Primul nod e (12, 12, 0) si poti alege tranzitzia (12, 12, 0) -> (10, 10, 1) (alegi sa trimitzi nr maxim de oameni/canibali, i.e., 2 din fiecare). In nodul (10, 10, 1), poti alege tranzitia (10, 10, 1) -> (11, 11, 0) (alegi sa trimitzi inapoi nr minim de oameni/canibali, i.e., 1 din fiecare). And so on. Modulo neatentzie, drumul arata cam asa:
(12, 12, 0) -> (10, 10, 1) -> (11, 11, 0) -> (9, 9, 1) -> (10, 10, 0) -> (8, 8, 1) -> (9, 9, 0) -> (7, 7, 1) -> (8, 8, 0) -> (6, 6, 1) -> (7, 7, 0) -> (5, 5, 1) -> (6, 6, 0) -> (4, 4, 1) -> (5, 5, 0) -> (3, 3, 1) -> (4, 4, 0) -> (2, 2, 1) -> (3, 3, 0) -> (1,1, 1) -> (2, 2, 0) -> (0, 0, 1)
Pentru K >= 4, poti gasi intotdeauna o solutie de genul acesta pentru ca numarul de oameni/canibali de pe malul 0 scade monoton dupa fiecare drum dus-intors. (i.e., nu e nevoie de backtracking).
Acesta este un exemplu in care alegi dintre toti succesorii care minimizeaza |i - j| pe cel (sau unul dintre cei) care minimizeaza i + j. In general, ideea e cam aceeasi: Esti in nodul (i, j, k). Calculezi succesorii lui (i, j, k), e.g., toate nodurile (i', j', 1 - k) in care poti ajunge din (i, j, k). Dintre nodurile acestea, alegi pe cel care minimizeaza i' + j' (sau alt criteriu). Daca nodul (i, j, k) nu are succesori, faci backtracking.
|