$A[i][j] = min(A[i-1][j], A[i-1][j-V[i]]+1)$ unde $V[i]$ este greutatea obiectului $i$ ({$i ≤ N, j ≤ G$}).
Aceasta solutie are complexitate $O(N*G)$ si nu se incadreaza in timp datorila limitelor mari pentru $N$ si $G$. De asemenea, pentru reconstructie trebuie pastrata o matrice $T$ de dimensiune $N*G$, care nu incape in memorie. Deoarece avem numai greutati intre $1$ si $200$, putem folosi o alta abordare: $A[i][j]$ = numarul minim de obiecte necesare cu greutate $≤ i$ pentru a obtine o greutate $j$. Relatia de recurenta este:
$A[i][j] = min(A[i-1][j], A[i-1][j-i]+1, A[i-1][j-2*i]+2 ... A[i-1][j-C[i]*i]+C[i])$ unde $C[i]$ este numarul de obiecte de greutate $i$ care exista ({$i ≤ 200, j ≤ G$}).

 Exista o alta solutie dinamica (problema fiind asemanatoare cu problema cand trebuie sa platesti o suma cu un numar minim de bancnote cu valori date). Folosind matricea A[i,j] unde i este greutatea pe care vrem sa obtinem iar j ne arata daca am ales un anumit obiect sau nu, ne incadram usor in timp. A[i,0] este suma valorilor din coloana i. Deoarece obiectele au greutati intre 1 si 200 putem sa numaram cate avem asemanatori si astfel A[i,j] inseamna cate obiecte de greutatea j am folosit pentru greutatea totala i. Cand vrem sa calculam o coloana din matricea A, luam la rand greutatea obiectelor pe care avem la dispozitie (GR sa fie greutatea obiectului); Daca i-gr e un numar pozitiv atunci daca A[i-gr,0]>0 (am putut forma greutatea i-gr) si mai avem la dispozitie macar un obiect de greutatea gr (A[i-gr,gr]<CATE[gr]; CATE este un vector care ne arata cate obiecte avem de greutatea 1,2,3...200) si A[i-gr,0]+1<A[i,0] (bineinteles nu in cazul in care A[i,0]=0)) atunci valorile din coloana i-gr vor fi copiate in coloana i, si incrementam A[i,0] si A[i,gr]; La sfarsit cautam cea mai mare valoare a lui i pentru care A[i,0]>0. Singura problema este ca o matrice de 200*75000 e mult prea mare pentru 16MB. Solutia este sa nu pastram toata matricea A ci numai ultimele H linii (5000 de exemplu; 200*10000 incapa in memorie).

O implementare triviala ar avea aceeasi complexitate $O(N*G)$, dar putem imbunatati solutia folosind o structura de date numita _deque_. Puteti citi mai mult despre aceasta structura 'aici':http://infoarena.ro/USACO-dec-2004-divizia-GOLD (problema Divide), 'aici':http://infoarena.ro/preoni-2005/runda-3/solutii (problema Ferma) si 'aici':http://infoarena.ro/preoni-2006/runda-2/solutii (problema Struti).
Vom calcula elemente din linia $i$ a matricei astfel: intai elementele de forma $k*i$, apoi elementele $k*i+1$, $k*i+2$, ... $k*i+(k-1)$. Cand calculam $A[i][j]$ cu $j = k*i+r$ , vom avea in deque toate elementele $A[i-1][x*i+r] + (k-x)$ cu $k-C[i] ≤ x ≤ k$. Astfel $A[i][j]$ se detemrina in $O(1)$ folosind capatul stanga al deque-ului. Cand se trece la calculul elementului $(k+1)*i+r$ se elimina din deque elementul $A[i-1][(k-C[i])*i+r]+...$ , si se insereaza elementul $A[i-1][(k+1)*i+r]$. Conform relatiei, inainte de inserare toate elementele din deque ar trebui marite cu $1$, dar acest lucru este echivalent cu a scadea $1$ din elementul care se insereaza. Astfel, se poate determina matricea $A$ in timp $O(200*G)$. Deoarece se pot retine doar ultimele doua linii din matricea $A$ , memoria folosita este $O(G)$.
Desigur, pentru reconstituire ar trebui retinuta o alta matrice $T$ de dimensiuni $200*G$ ,dar nu este destula memorie pentru a construi o astfel de matrice. O solutie ar fi pastrarea liniilor din matricea $A$ din $√200$ in $√200$. O scurta descriere despre aceasta metoda gasiti 'aici':http://infoarena.ro/winter-challenge-1/solutii (problema Smen). Memoria folosita ar fi fost $O(√200*G)$.