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/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)$.