h3. (problema grea, clasele 11-12)
O prima solutie clasica ar fi folosind metoda programarii dinamice. Se construieste o matrice $A[i][j]$ = numarul minim de obiecte necesare din primele $i$ obiecte pentru a obtine o greutate $j$. Relatia de recurenta este:

$A[i][j] = min(A[i-1][j], A[i-1][j-V[i]]+1)$ unde $V[i]$ este greutatea obiectului $i$.

$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. exista 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.
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 elementul $(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.

$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$).
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 elementul $(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)$.

==Include(page="template/preoni-2007/footer")==