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 .

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.

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 obtine $50$ de puncte.