h2. Date de intrare
Pe prima linie a fişierul $rucsac.in$ se vor gasi valorile $N$ si $G$, cu semnificatia din enunt. Pe urmatoarele $N$ linii se vor gasi perechile de valori $w{~i~}$ si $p{~i~}$, reprezentand greutatea, respectiv profitul obiectului $i$.
Pe prima linie a fişierul $rucsac.in$ se vor gasi valorile $N$ si $G$, cu semnificatia din enunt. Pe urmatoarele $N$ linii se vor gasi perechile de valori $W{~i~}$ si $P{~i~}$, reprezentand greutatea, respectiv profitul obiectului $i$.
h2. Date de ieşire
În fişierul de ieşire $rucsac.out$ se va afisa o singura valoare $P$, profitul maxim care poate fi obtinut respectand conditia problemei.
În fişierul de ieşire $rucsac.out$ se va afisa o singura valoare $P{~max~}$, profitul maxim care poate fi obtinut respectand conditia problemei.
h2. Restricţii
* $1 ≤ N ≤ 5000$
* $1 ≤ G ≤ 10000$
* $0 ≤ W{~i~}, P{~i~} ≤ 10000$
h2. Exemplu
table(example). |_. rucsac.in |_. rucsac.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 10
3 7
3 4
1 2
1 9
2 4
1 5
| 29
|
h3. Explicaţie
...
Luam obiectele $1, 2, 4, 5$ si $6$, a caror greutate este $10$, iar suma profiturilor este $29$.
h2. Indicatii de rezolvare
Problema rucsacului reprezinta un exemplu clasic al utilizarii programarii dinamice. Solutia pe care urmeaza a o prezenta ruleaza in timp pseudo-polinomial $O(N*G)$, si foloseste $O(N*G)$ memorie. O descriere mai completa a problemei si a variatelor ei este disponibila pe 'Wikipedia':http://en.wikipedia.org/wiki/Knapsack_problem .
Vom tine un tablou bidimensional $D$, care va retine in celula de coordonate $(i, cw)$ profitul maxim pe care-l putem obtine selectand o submultime a primelor $i$ elemente, a caror greutate insumata este egala cu $cw$. Presupunem ca avem calculate solutiile pentru orice greutate mai mica sau egala ca $G$, selectand o submultime din primele $i-1$ elemente. Construim solutia pentru $i$ elemente, folosindu-ne de urmatoarea recurenta: $D[i][cw] =$ maximul dintre $D[i-1][cw]$, situatie in care nu adaugam elementul $i$ la solutia precedenta, si $D[i-1][cw - W[i]] + P[i]$, cand adaugam la cea mai buna solutie cu greutatea $cw - W[i]$ elementul $i$, obtinand greutatea $W[i]$ si un profit mai mare cu $P[i]$. Raspunsul final se va afla in starea $D[N][G]$. Aceasta 'solutie':job_detail/608481?action=view-source obtine $50$ de puncte.
Pentru '$100$ de puncte':job_detail/608485?action=view-source este necesar sa facem urmatoarea observatie: pentru o anumita linie din dinamica, recurenta nu se foloseste decat de linia precedenta, deci retinerea intregului tablou este inutila. In schimb, vom retine doar ultimele doua linii din matrice, reducand memoria la $O(N)$. De asemenea putem sa reţinem tot timpul o singura linie, dacă parcurgem linia în sensul invers al greutăţilor, cum puteti observa in aceasta 'solutie':job_detail/681297?action=view-source.
Mentionez ca exista si algoritmi greedy care, desi ruleaza intr-o complexitate a timpului cu mult sub cea a solutiei prezentate, nu reusesc sa ofere rezultatul corect, ci doar sa-l aproximeze.
h3. Probleme propuse:
* 'Triunghi':problema/triunghi
* 'Energii':problema/energii
* 'Lapte':problema/lapte
* 'Calatorie interplanetara':problema/calatorie
* 'Jocul':problema/jocul
* 'Ghiozdan':problema/ghiozdan
* 'Intensitate':problema/intensitate
== include(page="template/taskfooter" task_id="rucsac") ==
