h2. Exemplu
|_. hoata.in |_. hoata.out |

|lol|ii|
|
3
2 1 3
10 2 1
9 1 2
2 2 3
10 2 1
9 1 2
2 3 3
10 2 1
9 1 2
|
27
46
-1
|

h2. Explicaţie

h3. Explicaţie

Sunt T = 3 scenarii.

h3. Primul scenariu

h4. Primul scenariu

Avem N = 2 camere şi K = 1 hoţ înzestrat cu un rucsac de capacitate G = 3. În camera 1 se afla o
rezervă infinită de lingouri de aur de valoare 10 şi greutate 2, iar în camera 2 se află o rezervă infinită
de lingouri de aur de valoare 9 şi greutate 1. Alarma dintre camera 1 şi camera 2 are x{~1~} = 1, iar alarma
dintre camera 2 şi ieşire are x{~2~} = 2. În condiţiile date alarmele nu vor suna indiferent ce alege să facă
hoţul, aşa că acesta poate obţine o captura maximă de 27 = 9 + 9 + 9 furând trei lingouri din camera 2.

h3. Al doilea scenariu

h4. Al doilea scenariu

Acest scenariu este identic cu primul, doar că avem K = 2 hoţi, fiecare având cate un rucsac de capacitate 3. Dacă ambii hoţi iau câte 3 lingouri din camera 2, atunci aceştia ar avea o captură totală de 54 = 6 × 9. Din păcate, dacă ar face acest lucru, ei ar fi prinşi de alarma dintre camerele 1 şi 2. +Observăm că ei ar fi prinşi de aceasta alarmă chiar şi dacă aleg sa nu fure nimic din nicio cameră!+ Captura maximă, de fapt, se obţine, de exemplu, dacă primul hoţ alege să fure câte un lingou din fiecare cameră (total 19 = 10 + 9), iar al doilea hoţ alege să fure trei lingouri din camera 2 (total 27 = 9 + 9 + 9).
În total 46 = 19 + 27.