Curs 9. Programare dinamica.
-Probleme de optimizare (min, max, cel mai lung/scurt drum
/subsecventa etc.)
Daca optimul exista, programarea dinamica il gaseste sigur.
Cinci pasi de baza:
1. Se imparte problema complexa in subprobleme mai simple
2. Gaseste solutii optime ale acestor subprobleme.
3. Stocheaza rezultatele subproblemelor (Memorizare)
4. Refoloseste aceste rezultate, astfel incat sa nu trebuiasca sa le
recalculezi din nou
5. In final, calculeaza rezultatul problemei mari.
Programarea dinamica este aplicabila acelor probleme care: contin
subprobleme ce se suprapun, si care au sub-structura optimala.
(solutia optima a problemei mari poate fi obtinuta prin combinarea
solutiilor optime ale subproblemelor)
1 + 1+ 1+ 1
2
3
4.... (nu trebuie recalculat mereu)
-Complexitatea de stocare creste, scade complexitatea raportata la
timp.
Exemplu. Calculul seriei Fibonacci.
0 1 1 2 3 5 8 13 ...
1
Functie recursiva simpla
Int fib(n)
{if(n<0)error;
if(n==0)return 0;
if(n==1)return 1;
sum=fib(n-1)+fib(n-2);
return sum;}
Cate apeluri? Modificati codul astfel incat sa va afiseze numarul de
apeluri. Desenati arborele apelurilor. Numar exponential de apeluri
catre subrutinele recursive (O(2n))...
Programare dinamica metoda TOP DOWN (cu memorizare):
Memo = (-1,-1,-1,-1,-1,-1)
Int fib(n)
{if(memo[n]!=-1) return memo[n];
if(n<0)error;
if(n==0)return 0;
if(n==1)return 1;
sum=fib(n-1)+fib(n-2);
memo[n]=sum;
return sum;}
2
Programare dinamica metoda BOTTOM UP (CALCUL TABELAR)
A=(0,1,...)
Int fib(int n)
{int A[];
A[0]=0;A[1]=1;
For (i=2;i<=n;i++)
A[i]=A[i-1]+A[i-2]}
return A[n];}
Problema calculului unei valori
a1+a2+...+an [1..n]
Generalizare: ai+...+aj [i..j] (i<j)
dependențe
-punem in evidenta un arbore cu radacina (1,n)- un PD arbore (din
orice varf putem ajunge in radacina).
-punem in evidenta un sistem de dependente care creeaza un PD-
arbore ⇒ parcurgem in postordine acest PD-arbore; mergem de la
frunze spre radacina (echivalent cu DivImp : descompunere plus
compunerea rezultatelor).
3
Alaturi de GREEDY, programarea dinamica duce, de cele mai multe
ori, la un timp de calcul polinomial. Se aplica unui anumit tip de
probleme:
D1 D2 Dn
S0 S1 S2 ... Sn-1 Sn
Daca D1,... , Dn este un sir de decizii care conduce sistemul in mod
optim din starea S0 in starea Sn, atunci trebuie indeplinita una din
conditiile urmatoare (principiul de optimalitate):
[Link],...,Dn este un sir de decizii ce conduce optim sistemul din starea
Sk-1 in starea Sn , ꓯ k=1,n (METODA INAINTE)
2. D1,...,Dk este un sir de decizii ce conduce optim sistemul din starea
S0 in starea Sk , ꓯ k=1,n (METODA INAPOI)
3. Dk+1,...,Dn ; D1,...,Dk sunt siruri de decizii ce conduc optim sistemul
din starea Sk in starea Sn , respectiv din starea S0 in starea Sk ꓯ k=1,n
(METODA MIXTA)
Programarea dinamica se poate aplica problemelor in care optimul
general implica optimul partial:
OPTIM GENERAL⇒OPTIM PARTIAL
Aceasta nu inseamna ca optimul partial implica pe cel general, dar
putem cauta optimul general intre optimele partiale (se reduce,
oricum, cautarea).
Etape de rezolvare:
1. Verificarea principiului de optimalitate
4
2. Scrierea unor relatii de recurenta care cuantifica modul de
obtinere al optimului general din optime partiale
3. Scrierea programului (!fara recursivitate: altfel se pierde
avantajul eficientei adus de programarea dinamica)
I. Metoda inapoi- EXEMPLE
[Link] cate moduri se poate plati o suma de bani cu diverse tipuri de
monezi (bani)
Se da: w- o suma ce trebuie platita
Valorile banilor: 1 leu, 3 lei, 10 lei etc (pp ca avem nr
NELIMITAT din fiecare denominatiune)
Se cere: in cate moduri putem plati w cu aceste tipuri de bani.
Exp. Valori bani ={1,2,3}
W=5 ⇒
(1,1,1,1,1)
(1,1,1,2)
(1,2,2)
(1,1,3)
(2,3) – 5 modalitati de plata
Solutia 1. Folosim recursivitate→complexitate exponentiala
Programarea dinamica stocheaza rezultatele partiale de care va mai
avea nevoie (nu le recalculeaza)- deci dureaza mai putin timp.
Solutia 2.
{2,3,5,10}
5
w=15
Se divide problema complexa in subprobleme (ca la DivImp).
Un tabel de stocare a rezultatelor partiale:
0 1 2 3 4 5 6 7 8 9 1 11 12 1 14 15
0 3
2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
3 1 0 1 0+1 1 1 2 1 2 2 2 2 3 2 3 3
5 1
10 1
0 1 2 3 4 5 6 7 8 9 1 11 12 1 14 15
0 3
2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
3 1 0 1 0+1 1 1 2 1 2 2 2 2 3 2 3 3
5 1 0 1 1 1 2 2 2 3 3 4 4 5 5 6 7
10 1 0 1 1 1 2 2 2 3 3 5 4 6 6 7 9
If (val moneda>w) then copiaza valoarea de pe randul de mai sus
[Link] moneda
[Link] moneda
[Link] 1 si 2.
a[i][0]=1; ꓯ i
for(i=1;i<=[Link];i++)
for(j=0;j<=suma;j++)
if (monezi[i]>j) a[i][j]=a[i-1][j];
6
else a[i][j]=a[i-1][j]+a[i][j-monezi[i]];
...
[Link] minim de monezi cu care se poate plati o suma de bani
Dezavantaj Greedy 1.
Monezi{1,5,6,9,} (in numar infinit);
Suma=11;
(9,1,1) – nu e optim (5,6,).
Greedy nu da mereu solutia optima, PD-da, daca solutia exista!
Dezavantaj Greedy 2.
Monezi{4,10,25} (in numar infinit);
Suma=41.
Cu Greedy: (25,10,4, ???)- nu gaseste solutie desi exista solutie (25,
4,4,4,4).
0 1 2 3 4 5 6 7 8 9 10
1 0 1 2 3 4 5 6 7 8 9 10
5 0 1 2 3 4 1 2 3 4 5 2
6 0 1 2 3 4 1 1 2 3 4 2
9 0 1 2 3 4 1 1 2 3 1 2
...
If (monezi[i]>j) a[i,j]=a[i-1,j]
else
a[i,j]=min{a[i-1,j],1+a[i][j-monezi[i]]}
...
Tema laborator. Programati acest exemplu.
7
3. Problema triunghiului
Se considera un triunghi de numere naturale format din n linii. Cu
ajutorul sau se pot forma sume de numere naturale:
-se porneste cu numarul din linia 1;
-sucesorul unui numar se afla pe linia urmatoare sub el (aceeasi
coloana) sau pe diagonala la dreapta (coloana creste cu 1)
Care este cea mai mare suma care se poate forma astfel si care sunt
numerele care o alcatuiesc?
Ex. n=4
3 5
6 3 4
5 6 1 4
S1=2+3+6+5=16
S2=2+5+4+1=12
...
Sk=2+3+6+6=17 (max.)
2n-1 sume posibile.
8
Daca avem un sir de n numere optim (formeaza suma maxima),
atunci numerele intre i+1 si n formeaza o suma maxima in raport cu
sumele care se pot forma incepand cu numarul preluat de pe linia i
→ Metoda inainte.
La primul pas se copiaza ultima linie din T (triunghiul initial) in
matricea auxiliara C.
1
C T
C[n,i]←T[n,i], i=1,n.
Pentru linia i (i<n), scriem relatiile de recurenta:
C[i,j]=max{T[i,j]+C[i+1,j], T[i,j]+C[i+1,j+1]};
i=1,n, j=1,i
i=4: 5 6 1 4
i=3: C[3,1]=max{6+5,6+6}=12
C[3,2]=max{3+6,3+1}=9
C[3,3]=max{4+1,4+4}=8
C:
12 9 8
5 6 1 4
9
i=2
C[2,1]=max{3+12,3+9}=15
C[2,2]=max{5+9,5+8}=14
C:
15 14
12 9 8
5 6 1 4
i=1
C[1,1]=max{2+15,2+14}=17 (Suma maxima)
Var n,i,j:int;
T[][],c[][],drum[][]:int;
//citire T...
C[n,j]=T[n,j] ꓯ j=1,n
For i=n-1 downto 1 do
For j=1 to i do
If(c[i+1,j]<c[i+1,j+1]
{c[i,j]=t[i,j]+c[i+1,j+1];
drum[i,j]=j+1;}
else {c[i,j]=t[i,j]+c[i+1,j];
drum[i,j]=j;}
Suma maxima: c[1,1]. //afisare;
10
i=1;j=1;
while (i<=n) do
{write (t[i,j]); j=drum[i,j];i=i+1;} //afiseaza numerele ce formeaza suma
maxima.
4. Subsir crescator de lungime maxima
Se da un vector cu n elemente intregi. Sa se tipareasca cel mai lung
subsir crescator al acestuia.
Ex. V=(4,1,7,6,7) (n=5)
(4,7,7)
Idee: se calculeaza, pentru fiecare element al vectorului lungimea
celui mai lung subsir crescator care se poate forma incepand cu el.
Presupunem cel mai lung subsir care se poate forma cu elementul de
pe pozitia k a vectorului este Vi1,...,Vk,...Vip, (unde i1,... k, ...ip sunt
indicii termenilor subsirului relativ la vectorul dat) ⇒ Vk,...Vip este cel
mai lung subsir ce se poate forma incepand cu elementul Vk⇒ se
aplica Metoda Inainte.
L(k)=lungimea celui mai lung subsir crescator ce se poate forma
incepand cu elementul k al vectorului:
L(k)={1+maxL(i)| V(i)>=V(k), i={k+1,...,n}}
(elementele mai mari sau egale cu Vk, situate in dreapta sa).
Pentru vectorul exemplu: L=(3,3,2,2,1)
Var v,l: int[];
n,i,k,max,t:int;
11
begin
read(n); for i=1 to n do read(v[i]);
l[n]=1;
for k=n-1 downto 1 do
{max=0;
for i=k+1 to n do
if(v[i]>=v[k])&&(l[i]>max)
max=l[i];
l[k]=max+1;}
(//cu i se poate forma subsir mai lung)
//Maxim global:
max=l[1];t=1;
for k=1 to n do if (l[k]>max) then {max=l[k];t=k;} //t –poz de inceput a
subsirului
write (‘lungimea maxima’;max); write (v[t]);
for i=t+1 to n do
if (v[i]>=v[t])&&(l[i]==max-1) then {write(v[i]; max--;}.
12