h2. 'Banuti':problema/banuti
Notam cu $min$ valoarea minima. Se observa ca pentru o suma oarecare $s$, daca toate sumele din intervalul $(s,s+min]$ pot fi obtinute, atunci toate sumele $>s$ pot fi obtinute la randul lor. (Pentru a va convinge, in caz ca aveti neclaritati, simulati un knapsack).
Se construieste un graf cu $min$ noduri, nodul $x$ semnificand restul $x$ la impartirea cu $min$. Se defineste $cost[x]$, suma minima care poate fi obtinuta $(s)$, cu proprietatea ca $s%min=x$ (restul impartirii sumei la $min$ este $x$); $cost@[0]@=0$. Se observa ca daca putem obtine o suma $s$, atunci putem obtine toate sumele $s+k*min$ (care au acelasi rest), unde $k>0$. In acest graf fiecare bancnota (de valoare $v$), formeaza o muchie intre nodul $y$ si nodul $(y+v)%min$, cu costul $v$, unde $y$ apartine $[0,min)$. Daca acest graf nu este conex atunci nu avem solutie. Daca este conex, atunci solutia se afla in $max(cost[x])$, $x$ apartine $[0,min)$, care poate fi aflata cu Dijkstra. Mentionez faptul ca graful ar avea teoretic $N*min$ muchii. Pe cazul general, $N>min$, deci unele muchii sunt in plus (conform principiului cutiei) deci graful real ar trebui sa aiba $~min^2^$ muchii. Complexitatea finala este $O(min^2^)$.
Se construieste un graf cu $min$ noduri, nodul $x$ semnificand restul $x$ la impartirea cu $min$. Se defineste $cost[x]$, suma minima care poate fi obtinuta $(s)$, cu proprietatea ca $s%min=x$ (restul impartirii sumei la $min$ este $x$); $cost[@0@]=0$. Se observa ca daca putem obtine o suma $s$, atunci putem obtine toate sumele $s+k*min$ (care au acelasi rest), unde $k>0$. In acest graf fiecare bancnota (de valoare $v$), formeaza o muchie intre nodul $y$ si nodul $(y+v)%min$, cu costul $v$, unde $y$ apartine $[0,min)$. Daca acest graf nu este conex atunci nu avem solutie. Daca este conex, atunci solutia se afla in $max(cost[x])$, $x$ apartine $[0,min)$, care poate fi aflata cu Dijkstra. Mentionez faptul ca graful ar avea teoretic $N*min$ muchii. Pe cazul general, $N>min$, deci unele muchii sunt in plus (conform principiului cutiei) deci graful real ar trebui sa aiba $~min^2^$ muchii. Complexitatea finala este $O(min^2^)$.
h2. 'Renovare':problema/renovare
