1 9
2 4
1 5
| 27
| 29
|
h3. Explicaţie
Luam obiectele $1, 3, 4, 5$ si $6$, a caror greutate este $8$, iar suma profiturilor este $27$.
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/607584?action=view-source obtine $50$ de puncte.
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/607585?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)$.
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.
