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)$.
Din fericire existe o metoda _divide et impera_ mult mai usor de implementat pentru a reconstitui solutia folosind doar $O(G)$ memorie. Presupunem ca rezolvam problema initiala folosind dinamica de mai sus si pastrand doar ultimele doua linii din matrice. Stim acu ca greutatea maxima care se poate obtine este $H ≤ G$. Consideram o solutie optima (cu numar minim de obiecte) de a lua obiecte in ghiozdan de greutate $H$. Putem imparti aceasta solutie in doua bucati: sa determinam o solutie optima de a obtine greutatea $X$ folosind  obiecte cu greutati $≤ 100$ si o solutie optima de a obtine greutatea $H-X$ folosind obiecte cu greutati $> 100$. Putem determina aceasta valoare $X$ in timp ce facem dinamica initiala (folosind inca o matrice $B$ si pastrand ultimele doua linii) si apoi putem rezolva recursiv cele doua subprobleme. Asfel, la fiecare pas avem un interval $[st...dr]$ in care sunt greutatile pe care le folosim si o valoare $x$ care reprezinta greutatea pe care vrem s-o obtinem. La fiecare apel putem folosi aceleasi matrici, deci necesarul de memorie nu va depasi $O(G)$. Vom face si o analiza a complexitatii. Fie $T(st, dr, x)$ complexitatea pentru a rezolva o subproblema.
$T(st, dr, x) = O((dr-st+1)*x) + T(st, (st+dr)/2, y) + T((st+dr)/2+1, dr, x-y)$

Se poate demonstra prin inductie ca $T(st, dr, x) = $O((dr-st+1)*x)$.

Se poate demonstra prin inductie ca $T(st, dr, x) = O((dr-st+1)*x)$.

O prezentarea mult mai detaliata a acestei metoda si despre cum aceasta se poate aplica pentru a determina cel mai lung subsir comun a doua siruri folosind memorie liniara gasiti 'aici':http://www.ics.uci.edu/~eppstein/161/960229.html.
==Include(page="template/preoni-2007/footer")==