h2. 'Cascaval':problema/cascaval
Rezolvarea problemei incepe cu o observatie ne neaparat evidenta. Sa presupunem ca in luna $j$, compania are $X$ kilograme de cascaval (produse in luna respectiva sau in lunile anterioare si stocate pana in luna $j$). Sa presupunem, de asemenea, ca aceste $X$ kilograme provin din productia de cascaval din $2$ luni diferite, $i1$ si $i2$. Vom calcula costurile obtinerii celor $X1$ si celor $X2$ kilograme de cascaval:
* $C1 = F{~i1~} + C{~i1~} * X1 + (S{~i1~} + S{~i1+1~} + .. + S{~j-1~}) * X1 = A1 + B1 * X1$
* $C2 = F{~i2~} + C{~i2~} * X2 + (S{~i2~} + S{~i2+1~} + .. + S{~j-1~}) * X2 = A2 + B2 * X2$
Costul total pentru a avea $X$ kilograme in luna $j$ este $C1+C2$. Voi arata ca s-ar obtine un cost mai bun daca toate cele $X$ kilograme de cascaval ar fi produse in luna $i1$ sau in luna $i2$. Daca am produce toate cele $X$ kilograme in luna $i1$ si costul obtinut ar fi mai mic sau egal cu $C1+C2$, am avea urmatoarea relatie:
$A1+B1*(X1+X2) ≤ A1+B1*X1+A2+B2*X2$, care devine $B1*X2 ≤ A2+B2*X2$ si apoi $(B1-B2)*X2 ≤ A2$ $(1)$
In mod similar, daca toate cele $X$ kilograme ar fi produse in luna $i2$ si costul obtinut ar fi mai mic sau egal cu $C1+C2$, s-ar obtine relatia: $(B2-B1)*X1 ≤ A1$ $(2)$
Pentru a demonstra afirmatia, ar trebui ca cel putin una dintre relatiile $(1)$ si $(2)$ sa fie adevarata. Acest lucru este evident. Sa presupunem ca $B1 ≥ B2$. In acest caz, in relatia $(1)$, am avea in partea stanga o valoarea mai mica sau egala cu $0$, iar in partea dreapta o valoarea mai mare sau egala cu $0$. Deci relatia $(1)$ este adevarata. Daca $B1 ≤ B2$, atunci se observa in mod similar ca relatia $(2)$ este adevarata.
Concluzia la care ajungem este ca daca intr-o luna $j$ compania are $X$ kilograme de cascaval, acestea au fost produse toate in aceeasi luna $i ≤ j$. Aceasta concluzie ne permite sa gandim problema in urmatorul mod: In luna $1$ sunt produse un numar suficient de kilograme de cascaval pentru a satisface cererile din lunile $1, 2, .., a$. In luna $a+1$ se produc atatea kilograme de cascaval cate sunt necesare pentru a satisface cererile din lunile $a+1, a+2, .., b$ s.a.m.d. Acest mod de a privi problema ne duce usor cu gandul la o solutie folosind programare dinamica.
h3. Programare dinamica cu complexitatea $O(N^3^)$
Vom calcula costurile $cmin[i]$, reprezentand costul total minim pentru a satisface cererile din lunile $1, 2, .., i$. Algoritmul este descris in continuare in pseudocod:
* $cmin[ 0 ] = 0$
* $pentru i de la 1 la N$
** $cmin[i]=infinit$
** $pentru j de la 1 la i$
*** $cost_total = cmin[j-1] + F[j] + C[j] * D[j]$
*** $cost_stocare=S[j]$
*** $pentru k de la j+1 la i$
**** $cost_total = cost_total + (C[j]+cost_stocare) * D[k]$
**** $cost_stocare = cost_stocare + S[k]$
*** $daca cost_total < cmin[i] atunci$
**** $cmin[i]=cost_total$
Se variaza valoarea lui $i$ de la $1$ la $N$ si pentru fiecare valoare incercam sa calculam $cmin[i]$. Pentru aceasta, incercam toate valorile $j ≤ i$ care pot reprezenta luna in care sunt produse kilogramele de cascaval necesare in luna $i$. Apoi calculam costul total pentru cazul in care luna $j$ produce cantitatea de cascaval necesara pentru a satisface cererile din lunile $j, j+1, .., i$. In cele din urma vom avea in $cmin[i]$ minimul dintre costurile corespunzatoare fiecarei variante de alegere a lunii $j$. Costul total minim pentru toate cele $N$ luni il avem in $cmin[N]$. Bineinteles, aceasta solutie nu se incadreaza in limita de timp.
he. Programare dinamica cu complexitatea $O(N^2^)$
Algoritmul descris anterior are complexitatea $O(N^3^). El se poate optimiza, insa, usor la complexitatea $O(N^2^)$.
* $cmin[ 0 ] = 0$
* $pentru i de la 1 la N$
** $cmin[i] = infinit$
** $dtotal = 0$
** $cost_stocare = 0$
** $pentru j de la i la 1$
*** $cost_stocare = cost_stocare + S[j] * dtotal$
*** dtotal = dtotal + D[j]
*** cost_productie = F[j] + C[j] * dtotal
*** cost_total = cmin[j-1] + cost_productie + cost_stocare
*** daca cost_total < cmin[i] atunci
**** cmin[i]=cost_total
Optimizarea adusa este minora, dar importanta. In algoritmul anterior, cel de-al treilea ciclu era folosit pentru a aduna la costul total costul stocarii cantitatilor de cascaval. In varianta optimizata, am schimbat sensul de parcurgere al variabilei $j$ si, in felul acesta, putem calcula pe parcurs o parte din costul de stocare. Practic, la inceputul fiecarei iteratii din cel de-al doilea ciclu, $cost_stocare$ retine costul stocarii cantitatiior de cascaval din lunile $j+1, .., i$, el trebuind actualizat doar cu costul de stocare din luna $j$.
h3. Programare dinamica cu complexitatea $O(N*log^2^N)$
Aceasta solutie este semnificativ diferita fata de primele doua si presupune cunoasterea structurii de date numita arbore de intervale. De data aceasta vom privi problema usor diferit. In principiu, vom dori sa calculam acelasi lucru ca si in solutiile anterioare, si anume $cmin[i]$, reprezentand costul total minim pentru a satisface cererile din primele $i$ luni. Cand calculam $cmin[i]$ putem alege luna $j$ in care se produce cantitatea de cascaval necesara in luna $i$ dintre $i$ valori $(1,2,..,i)$. Vom privi aceste $i$ optiuni ca pe niste functii $f1, f2, .., fi$. Valoarea unei functii $fj$ in punctul $x$, $fj(x)$, reprezinta costul total minim pentru satisfacerea cererilor din primele $x$ luni, in cazul in care luna $j$ a fost aleasa pentru productia cantitatii de cascaval necesara in luna $x$.
Solutia va contine ciclul principal existent si in solutiile anterioare, in care este variata valoarea lui $i$. Pentru fiecare valoare a lui $i$ apare o functie noua $(fi)$, iar noi trebuie sa evaluam valoarea minima $fj(i)$ dintre toate functiile existente $(f1, f2, .., fi)$.
Inainte de trece mai departe vom introduce doi noi vectori $SP$ si $DP$, reprezentand sume partiale ale costurilor de stocare si ale cantitatilor de cascaval cerute:
* $SPi = S1 + S2 + .. + Si$
* $DPi = D1 + D2 + .. + Di$
In continuare vom defini mai detaliat functiile $fj$ care ne intereseaza. O functie $fj$ apare la momentul $j$ si este definita doar pentru valori $x$ de la $j$ la $N$. Valoarea initiala a functiei este: $fj(j)$ este: $fj(j) = cmin[j-1] + Fj + Cj * Dj$.
Diferenta dintre doua valori consecutive ale functiei este: $Delta fj(i) = fj(i) - fj(i-1) = Cj * Di + (Sj + Sj+1 + .. + Si-1) * Di$
Aceasta diferenta reprezinta cu cat creste functia fata de momentul anterior. Diferenta contine costul necesar productiei a $Di$ kilograme in luna $j$ si costul necesar stocarii acestei cantitati din luna $j$ (inclusiv) pana in luna $i$ (exclusiv). Diferenta poate fi scrisa folosind vectorul $SP$ introdus anterior, astfel: $Delta fj(i) = Cj * Di + (SPi-1 - SPj-1) * Di$.
Putem rescrie aceasta diferenta intr-un mod si mai convenabil, in felul urmator: $Delta fj(i) = SPi-1 * Di + (Cj - SPj-1) * Di$. Observam ca diferenta consta dintr-un termen ce depinde doar de punctul in care se evalueaza functia $(i)$ si un termen ce reprezinta un produs dintre un factor ce depinde doar de definitia functiei (constant pentru functia $fj$) si un factor ce depinde doar de punctul in care este calculata functia. Vom nota valoarea $Cj - SPj-1$ cu $Pj$.
Sa ne gandim ce efect are acest mod de scriere al diferentei dinte doua valori consecutive ale unei functii $fi$. In momentul in care trecem de la valoarea $i-1$ la valoarea $i$, toate functiile $fj$ anterioare cresc cu aceeasi valoare $SPi-1 * Di$, precum si cu produsul $Pj * Di$. Singurul inconvenient in tratarea unitara a tuturor functiilor existente la momentul $i$ este reprezentat de aparitia unei functii noi, $fi$. Pentru aceasta, vom schimba putin definitia functiilor. Vom considera ca fiecare functie $fi$ are o valoare initiala in punctul $i-1$, chiar daca ea nu exista, practic, la momentul $i-1$: $fi(i-1) = cmin[i-1] + Fi$
In felul acesta, avem $Delta fi(i) = fi(i) - fi(i-1) = Ci * Di = (Ci + SPi-1 - SPi-1) * Di = SPi-1 * Di + (Ci - SPi-1) * Di = SPi-1 * Di + Pi * Di.$
Folosind aceasta scriere, putem considera ca toate functiile $fj$ $(j=1,..,i)$ au crescut de la pasul $i-1$ la pasul $i$ cu o valoare $Delta fj(i)$ definita in mod unitar.
Revenind la solutie, la fiecare pas $i$ va trebui sa determinam minimul dintre valorile $fj(i)$, cu $j$ de la $1$ la $i$ si sa atribuim acest minim lui $cmin[i]$. O solutie care ar calcula valoarea fiecarei functii ar fi prea lenta, avand complexitatea $O(N^2^)$. Chiar si excluzand functiile care nu mai au sanse sa fie minime in viitor, solutia tot nu ar obtine punctaj maxim, din cauza depasirii limitei de timp (totusi, solutia nu trebuie exclusa de la bun inceput, deoarece, cu niste optimizari minore, ea va avea complexitatea $O(N * numarul de functii candidate "active")$, iar numarul de functii candidate "active" este, in cele mai multe cazuri, semnificativ mai mic decat $N$). In continuare va fi prezentata o modalitate eficienta de determinare a acestei valori minime.
Intai sa observam ca orice valoare $cmin[i]$ contine o suma de valori constante, pe care le putem calcula de la inceput. $cmin[i]$ va contine suma valorilor $(SPj-1 * Dj)$ (cu $j$ de la $1$ la $i$). Aceasta este suma termenilor comuni fiecarei $Delta fj$. Prin urmare, vom modifica definitiile functiilor noastre pentru a exclude aceasta suma de valori constante si vom adauga suma respectiva la sfarsit, cand vom afisa rezultatul.
Asadar, vom considera ca $Delta fj(i) = (Cj - SPj-1) * Di = Pj * Di$. Conform acestei noi definitii, valorile calculate $cmin[i]$ nu mai au semnificatia initiala. Totusi, adaugand la valoarea $cmin[N]$ pe care o vom obtine folosind noile definitii ale functiilor, suma precizata, vom obtine costul total minim dorit. Avantajul excluderii acestei sume din calculul valorilor $cmin[i]$ va fi vizibil in continuare.
Sa consideram o reprezentare in plan a functiilor $fj$, in care abscisele $x$ iau valori de la $0$ la $N$, iar ordonatele corespund valorilor functiilor $fj$. Aceste valori pot fi acum si negative, doarece $Pj$ poate fi o valoare negativa. Aceasta reprezentare ne este folositoare doar daca o modificam in felul urmator: abscisa corespunzatoare lunii $i$ este $DP[i]$. Folosind reprezentarea in plan modificata, se observa ca functiile $fj$ sunt niste semidrepte. Acest lucru este evident si din definitia lor. Ele pornesc de la o valoare initiala si apoi cresc pentru fiecare unitate a coordonatei $x$ cu o valoare egala cu $Pj$, corespunzand pantei semidreptei.
In acest caz, fiecare functie $fj$ are valoarea minima dintre toate functiile pe un interval de abscise $[lj, rj]$ sau nu are niciodata valoarea minima dintre toate functiile. Acest lucru se poate demonstra usor. Sa presupunem ca functia $fj$ este minima pe doua intervale disjuncte $[lj1, rj1]$ si $[lj2, rj2]$, cu $lj2 > rj1$. Sa presupunem ca la abscisa $rj1$, o alta functie $fk$ a depasit functia $fj$. Mai exact, functia $fk$ avea valori mai mari decat functia $fj$, iar dupa momentul $rj1$ a atins valori mai mici. Pentru ca o functie sa o depaseasca pe alta, este necesar ca panta functiei respective sa aiba o valoare mai mica decat a functiei depasite. Prin urmare, $Pk < Pj$. Dar in aceste conditii, de la abscisa $rj1$ incolo, functia $fk$ va avea mereu valori mai mici decat functia $fj$, astfel ca functia $fj$ nu va mai fi niciodata minima. O alta situatie in care functia $fj$ ar putea sa nu mai fie minima dupa abscisa $rj1$ este pentru ca a aparut o functie $fk$ cu o valoare initiala mai mica decat $fj$, dar o panta mai mare, astfel ca, in cele din urma, functia $fj$ o va depasi pe functia $fk$ si va redeveni minima. Aceasta situatie este si ea imposibila, din modul de calcul al valorii initiale al unei functii $fk$. Aceasta valoare initiala este valoarea minima a unei functii existente la momentul $k-1$, plus valoarea $Fk$ $(Fk ≥ 0)$, iar valoarea minima la momentul aparitiei functiei $fk$ este chiar valoarea functiei $fj$.
Folosind observatia ca fiecare functie este minima pe cel mult un interval, putem folosi un arbore de intervale pentru a stoca in el semidrepte. Aceasta este o utilizare oarecum neobisnuita a unui arbore de intervale, dar vom vedea ca este foarte utila in cazul acestei probleme. Pseudocodul solutiei este urmatorul:
* $; calculeaza vectorii SP si DP$
* $SP[0]=0$
* $DP[0]=0$
* $pentru i de la 1 la N$
** $SP[i]=SP[i-1]+S[i]$
** $DP[i]=DP[i-1]+D[i]$
* $; calculeaza vectorul cmin$
* $cmin[0]=0$
* $pentru i de la 1 la N$
** $finit[i]=cmin[i-1]+F[i]$
** $P[i]=C[i]-SP[i-1]$
** $[li,ri]=find_interval(i) ; gaseste intervalul [li,ri] pe care functia fi este minima$
** $daca intervalul [li, ri] nu este vid$
*** $update(li,ri,i,radacina_arborelui_de_intervale)$
** $cmin[i]=get_min(i) ; determina valoarea minima in punctul i dintre toate functiile existente$
* $suma=0$
* $pentru i de la 1 la N$
** $suma=suma+SP[i-1]*D[i]$
* $afisaza cmin[N]+suma$
Cele $3$ functii a caror implementare mai trebuie descrisa in detaliu sunt: $find_interval$, $update$ si $get_min$.
h4. Functia $find_interval$
Aceasta functie cauta binar, intre $i$ si $N$, prima luna $li$ in care functia $fi$ are o valoare mai mica decat toate celelalte functii. In mod similar se cauta binar si ultima luna $ri$ in care functia $fi$ are o valoare mai mica decat celelalte functii. Pentru a gasi capatul stanga al intervalului pe care o functie este minima, va trebui sa observam cum variaza functia in raport cu valoarea minima de la fiecare moment. O descriere generala a acestui comportament (care exclude cazurile particulare) este urmatoarea: la momentul aparitiei, functia va avea o valoarea mai mare decat valoarea minima din acel moment, apoi diferenta va scadea treptat, pana cand functia devine minima ; functia ramane minima pana la un anumit moment, dupa care diferenta dintre valorile functiei si valoarea minima creste. Acest comportament sugereaza ca trebuie folosita o cautare binara pe "derivata" functiei (adica pe diferentele dintre 2 valori consecutive ale functiei si valoarea minima a unei functii in punctele respective).
Pseudocodul pentru calculul capatului stanga al intervalului in care functia fi este minima este urmatorul:
*left=i
*right=N
*li=N+1
*cat timp left <= right
** mid = (left+right)/2
** fi_mid_1 = finit[i]+(DP[mid]-DP[i-1])*P[i] // valoarea in punctul DP[mid+1]
** fi_mid_2 = finit[i]+(DP[mid + 1]-DP[i-1])*P[i] // valoarea in punctul DP[mid]
** fmin1=get_min(mid+1) // valoarea minima in punctul DP[mid+1]
** fmin2=get_min(mid) // valoarea minima in punctul DP[mid]
** df1 = fi_mid_1 - fmin1;
** df2 = fi_mid_2 - fmin2;
** daca (df1 < 0)
*** li = mid;
*** right = mid - 1;
** altfel
** daca (df1 - df2 > 0)
*** left = mid + 1;
** altfel
*** right = mid - 1;
* ; la sfarsit, in li se afla capatul stanga al intervalului in care fi este minima (sau N+1 daca nu exista un astfel de interval)
Functiile $update$ si $get_min$ se aplica arborelui de intervale si au complexitate $O(logN)$. Complexitatea functiei $find_interval$ este $O(log^2^N)$.
Fiecare nod al arborelui de intervale memoreaza indicele $i$ al unei semidrepte al carei interval $[li,ri]$, in momentul determinarii acestuia, continea complet intervalul corespunzator nodului din arborele de intervale. De asemenea, fiecarui nod al arborelui de intervale ii corespunde un interval $[ l[nod], r[nod] ]$.
h4. Functia $update$
Pseudocodul functiei $update$ este prezentat in continuare:
* $*update(li,ri,i,nod)*$
* $daca intervalul corespunzator nodului nod este chiar [li,ri], atunci$
** $index[nod]=i$
* $altfel$
** $fs = fiul stanga al nodului nod$
** $fd = fiul dreapta al nodului nod$
** $daca l[fd] > ri atunci$
*** $update(li,ri,i,fs)$
** $altfel$
** $daca r[fs] < li atunci$
*** $update(li,ri,i,fd)$
** $altfel$
*** $update(li,r[fs],i,fs)$
*** $update(l[fd],ri,i,fd)$
h4. Functia $get_min$
Fiecare nod din arbore are o referinta catre tatal sau $(tata[nod])$. Radacina arborelui are o referinta catre o valoare nedefinita $(NEDEFINIT)$. Pseudocodul functiei $get_min$ este urmatorul:
* $get_min(i)$
* $nod = nodul din arbore corespunzator intervalului [i,i]$
* $val_min=infinit$
* $cat timp nod <> NEDEFINIT$
** $k=index[nod]$
** $daca k este definit atunci$
*** $fki = finit[k] + (DP[i] - DP[k-1]) * P[k]$
*** $daca fki < val_min atunci$
**** $val_min=fki$
** $nod=tata[nod]$
* $intoarce val_min$
h3. Link-uri utile
* Un 'articol':http://dspace.mit.edu/bitstream/1721.1/5146/1/OR-238-90.pdf care prezinta o solutie a acestei probleme avand complexitate optima $O(N*logN)$
h3. Probleme asemanatoare
* 'Euro / BOI 2003':problema/euro
* 'Yogurt Factory / USACO 2005':http://acm.pku.edu.cn/JudgeOnline/problem?id=2393
* 'Branza':problema/branza
* 'Rompetrol':problema/rompetrol
h2. 'Cercuri3':problema/cercuri3
