Programarea Dinamica
Programare Dinamica
Programare dinamica presupune rezolvarea unei probleme prin descompunerea ei in subprobleme si rezolvarea acestora. Spre deosebire de divide-et-impera, subproblemele nu sunt disjuncte, ci se suprapun.
Pentru a evita recalcularea portiunilor care se suprapun, rezolvarea se face pornind de la cele mai mici subprobleme si folosindu-ne de rezultatul acestora calculam subproblema imediat mai mare. Cele mai mici subprobleme sunt numite subprobleme unitare. Acestea pot fi rezolvate intr-o complexitate constanta, ex: cea mai mare subsecventa dintr-o multime de un singur element.
Pentru a nu recalcula solutiile subproblemelor ce ar trebui rezolvate de mai multe ori, pe ramuri diferite, se retine solutia subproblemelor folosind o tabela (matrice uni, bi sau multidimensionala in functie de problema) cu rezultatul fiecarei subprobleme. Aceasta tehnica se numeste memorizare.
Aceasta tehnica afla „valoarea” solutiei optime pentru fiecare din subprobleme. Mergand de la subprobleme mici la subprobleme din ce in ce mai mari ajungem sa gasim „valoarea” problemei intregi. Motivul pentru care aceasta tehnica se numeste Programare Dinamica este datorat flexibilitatii ei, „valoarea” schimbandu-si intelesul logic de la o Problema la alta. In probleme de minimizarea costului, „valoarea” este acest cost minim. In probleme de aflarea unei componente maxime, „valoarea” este dimensiunea componentei.
Dupa calcularea valorii pentru toate subproblemele se pot afla efectiv elementele ce alcatuiesc solutia.
„Reconstructia” solutiei se face mergand din subproblema in subproblema incepand de la problema cu valoarea optima si ajungand in subprobleme unitare. Metoda admite nuante in cazuri particulare, o sa se inteleaga mai bine din exemple.
Aplicand aceasta tehnica determinam una din solutiile optime, problema putand avea mai multe solutii optime. In cazul in care se doreste determinarea tuturor solutiilor optime, algoritmul trebuie combinat cu unul de backtracking in reconstructia solutiilor.
Dupa cum probabil ati intuit deja, diferenta majora dintre cele doua metode prezentate este ca algoritmul greedy mentine doar solutiile partiale de la pasul curent pentru a le folosi la pasul urmator, in timp ce programarea dinamica poate utiliza la un pas subsolutii generate la oricare alt pas anterior.
Programarea Dinamica poate fi descompusa in urmatoarea secventa de pasi:
1. Descoperirea structurii si “masurii” pe care o are o solutie optima.
2. Determinarea unei metode de calcul recursive pentru a afla valoarea fiecarei subprobleme.
3. Calcularea “de jos in sus” a acestei valori (de la subproblemele cele mai mici la cele mai mari)
4. Reconstructia solutiei optime pornind de la rezultatele obtinute anterior.
Exemple de probleme:
1.Determinarea celui mai lung subsir strict crescator dintr-un sir de numere. Un subsir al unui sir este format din caractere (nu neaparat consecutive) ale sirului respectiv, in ordinea in care acestea apar in sir.
Exemplu: şirul {2, 4, 3, 5, 3, 6} are cel mai lung subsir crescator de lungime 4: {2, 4, 5, 6} sau {2, 3, 5, 6}.
Rezolvare:
Soluţia problemei nu este unică, dar lungimea maximă a subşirului crescător, da.
Vom nota cu L[k] lungimea celui mai lung subşir crescător care începe de la poziţia k şi până la sfârşitul şirului iniţial. Calculăm, pe rând, L[n], L[n-1], L[n-2] … L[2], L[1]. Lungimea celui mai lung subşir crescător va fi dată de cea mai mare valoare a lui L.
L[n] = 1
L[k] = 1+ max {L[i ], unde k
#include
int v[10000],n,i,L[1000],max,mx,k,t;
void main(){
fstream f(“subsir.txt”,ios::in);
for(i=1;i<=n;i++) f>>v[i];
L[n]=1; subsir maxim de lung 1
for(k=n-1;k>0;k–)
{mx=0;
for(i=k+1;i<=n;i++)
if(v[i]>=v[k] && L[i]>mx)
mx=L[i];
L[k]=mx+1;
if(L[k]>max)
{max=L[k];
t=k;}
}
cout<<“lungimea maxima:”<
cout<
for(i=t+1;i<=n;i++)
if ((v[i]>=v[t]) && (L[i]==max-1))
{cout<
max–;}
}
2. Subşir comun maximal
Fie X=(x1, x2, …, xn) şi Y=(y1, y2, …, ym) două şiruri de n, respectiv m numere întregi. Determinaţi un subşir comun de lungime maximă.
Exemplu
Pentru X=(2,5,5,6,2,8,4,0,1,3,5,8) şi Y=(6,2,5,6,5,5,4,3,5,8) o soluţie posibilă este: Z=(2,5,5,4,3,5,8)
Rezolvare:
Notăm cu Xk=(x1, x2, …, xk) (prefixul lui X de lungime k) şi cu Yh=(y1, y2, …, yh) prefixul lui Y de lungime h. O subproblemă a problemei date constă în determinarea celui mai lung subşir comun al lui Xk, Yh. Notăm cu LCS(k,h) lungimea celui mai lung subşir comun al lui Xk, Yh. Utilizând aceste notaţii, problema cere determinarea LCS(n,m), precum şi un astfel de subşir.
Pentru a reţine soluţiile subproblemelor vom utiliza o matrice cu n+1 linii şi m+1 coloane, denumită LCS. Linia şi coloana 0 sunt iniţializate cu 0, iar elementul LCS[k][h] va fi lungimea celui mai lung subşir comun al şirurilor Xk şi Yh.
Vom caracteriza substructura optimală a problemei prin următoarea relaţie de recurenţă:
lcs[k][0]=lcs[0][h]=0, k din {1,2,..,n}, h din {1,2,..,m}
lcs[k][h]=1+lcs[k-1][h-1], dacă x[k]=y[h]
max{lcs[k][h-1], lcs[k-1][h]}, dacă x[k]<>y[h]
#include
int x[100],y[100],n,m;
int lcs[100][100],max;
void rezolva(){
for(int k=1;k<=n;k++)
for(int h=1;h<=m;h++)
if(x[k]==y[h]) lcs[k][h]=1+lcs[k-1][h-1];
else
if (lcs[k-1][h]>lcs[k][h-1]) lcs[k][h]=lcs[k-1][h];
else lcs[k][h]=lcs[k][h-1];
}
void afiseaza_solutie_max(int k,int h){
if(lcs[k][h])
if(x[k]==y[h])
{afiseaza_solutie_max(k-1,h-1);
cout<
else
{if (lcs[k][h]==lcs[k-1][h])
afiseaza_solutie_max(k-1,h);
else if (lcs[k][h]==lcs[k][h-1])
afiseaza_solutie_max(k,h-1);
}
}
void main(){
ifstream f(“lcs.txt”,ios::in);
f>>n>>m;
for(int i=1;i<=n;i++) f>>x[i];
for(i=1;i<=m;i++) f>>y[i];
rezolva();
afiseaza_solutie_max(n,m);
}
3. Sumă maximă în triunghi
Fie triunghiul format din n linii (1
Determinaţi cea mai mare sumă de numere aflate pe un drum între numărul de pe prima linie şi un număr de pe ultima linie. Fiecare număr din acest drum este situat sub precedentul, la stânga sau la dreapta acestuia.
Rezolvare
1. Vom reţine triunghiul într-o matrice pătratică T, de ordin n, sub diagonala principală. Subproblemele problemei date constau în determinarea sumei maxime care se poate obţine din numere aflate pe un drum între numărul T[i ][j], până la un număr de pe ultima linie, fiecare număr din acest drum fiind situat sub precedentul, la stânga sau la dreapta sa. Evident, subproblemele nu sunt independente: pentru a calcula suma maximă a numerelor de pe un drum de la T[i ][j] la ultima linie, trebuie să calculăm suma maximă a numerelor de pe un drum de la T[i+1][j] la ultima linie şi suma maximă a numerelor de pe un drum de la T[i+1][j+1] la ultima linie.
2. Pentru a reţine soluţiile subproblemelor, vom utiliza o matrice suplimentară S, pătratică de ordin n, cu semnificaţia
S[i ][j]= suma maximă ce se poate obţine pe un drum de la T[i ][j] la un element de pe ultima linie, respectând condiţiile problemei.
Soluţia problemei va fi S[1][1].
3. Relaţia de recurenţă care caracterizează substructura optimală a problemei este:
S[n][ i]=T[n][i ], i din {1,2,…,n}
S[i ][j]=T[i ][j]+max{S[i+1][j], S[i+1][j+1]}
Secvenţa de program este:
for (i=1; i<=n; i++) S[n][i]=T[n][i];
for (i=n-1; i>=1; i–)
for (j=1; j<=i; j++)
{if (S[i+1][j]
else
S[i][j]=T[i][j]+S[i+1][j];}
SUMATRI.cpp
PROBLEME PROPUSE
1. Împărţirea unei mulţimi în 2 submulţimi de sume cât mai apropiate
La sfarsitul noptii de Craciun, Mosul a poposit la bradul a doi frati, unde si-a golit sacul. Cand s-au trezit, fratii au intrat intr-o mare dilema: cum isi vor imparti ei cadourile mosului? Stiind ca fiecare cadou are o valoare (cuprinsa intre 1 si 100 inclusiv) si ca sunt maxim 100 de cadouri scrieti un program care sa determine sumele cadourilor fratilor, precum si modul de impartire, astfel incat sumele obtinute sa fie cele mai apropiate posibil.
Date de intrare:
In fisierul CADOURI.IN se gasesc informaţiile referitoare la cadouri: pe prima linie numarul total de cadouri, pe urmatoarea linie valorile lor.
Date de iesire: In fişierul CADOURI.OUT trebuie scrise doua sume care sunt cele mai apropiate corespunzătoare unei impartiri a cadourilor, pe a doua linie valorile corespunzătoare cadourilor care însumează prima suma găsită, pe a treia linie, valorile corespunzătoare cadourilor care însumează a doua suma găsită.
Exemplu:
CADOURI.IN CADOURI.OUT
7 48 49
28 7 11 8 9 7 27 28 11 9
7 8 7 27
2. Sumă maximă
Se consideră un şir de N (N£1000) numere naturale cuprinse între 1 şi 10.000. Să se determine o sumă maximă de componente ale şirului astfel încât în sumă să nu intre două numere care se află pe poziţii consecutive în şir.
Exemplu: pentru şirul 1 10 2 40 100, suma maximă este 110 (10+100)
Programare dinamica presupune rezolvarea unei probleme prin descompunerea ei in subprobleme si rezolvarea acestora. Spre deosebire de divide-et-impera, subproblemele nu sunt disjuncte, ci se suprapun.
Pentru a evita recalcularea portiunilor care se suprapun, rezolvarea se face pornind de la cele mai mici subprobleme si folosindu-ne de rezultatul acestora calculam subproblema imediat mai mare. Cele mai mici subprobleme sunt numite subprobleme unitare. Acestea pot fi rezolvate intr-o complexitate constanta, ex: cea mai mare subsecventa dintr-o multime de un singur element.
Pentru a nu recalcula solutiile subproblemelor ce ar trebui rezolvate de mai multe ori, pe ramuri diferite, se retine solutia subproblemelor folosind o tabela (matrice uni, bi sau multidimensionala in functie de problema) cu rezultatul fiecarei subprobleme. Aceasta tehnica se numeste memorizare.
Aceasta tehnica afla „valoarea” solutiei optime pentru fiecare din subprobleme. Mergand de la subprobleme mici la subprobleme din ce in ce mai mari ajungem sa gasim „valoarea” problemei intregi. Motivul pentru care aceasta tehnica se numeste Programare Dinamica este datorat flexibilitatii ei, „valoarea” schimbandu-si intelesul logic de la o Problema la alta. In probleme de minimizarea costului, „valoarea” este acest cost minim. In probleme de aflarea unei componente maxime, „valoarea” este dimensiunea componentei.
Dupa calcularea valorii pentru toate subproblemele se pot afla efectiv elementele ce alcatuiesc solutia.
„Reconstructia” solutiei se face mergand din subproblema in subproblema incepand de la problema cu valoarea optima si ajungand in subprobleme unitare. Metoda admite nuante in cazuri particulare, o sa se inteleaga mai bine din exemple.
Aplicand aceasta tehnica determinam una din solutiile optime, problema putand avea mai multe solutii optime. In cazul in care se doreste determinarea tuturor solutiilor optime, algoritmul trebuie combinat cu unul de backtracking in reconstructia solutiilor.
Dupa cum probabil ati intuit deja, diferenta majora dintre cele doua metode prezentate este ca algoritmul greedy mentine doar solutiile partiale de la pasul curent pentru a le folosi la pasul urmator, in timp ce programarea dinamica poate utiliza la un pas subsolutii generate la oricare alt pas anterior.
Programarea Dinamica poate fi descompusa in urmatoarea secventa de pasi:
1. Descoperirea structurii si “masurii” pe care o are o solutie optima.
2. Determinarea unei metode de calcul recursive pentru a afla valoarea fiecarei subprobleme.
3. Calcularea “de jos in sus” a acestei valori (de la subproblemele cele mai mici la cele mai mari)
4. Reconstructia solutiei optime pornind de la rezultatele obtinute anterior.
Exemple de probleme:
1.Determinarea celui mai lung subsir strict crescator dintr-un sir de numere. Un subsir al unui sir este format din caractere (nu neaparat consecutive) ale sirului respectiv, in ordinea in care acestea apar in sir.
Exemplu: şirul {2, 4, 3, 5, 3, 6} are cel mai lung subsir crescator de lungime 4: {2, 4, 5, 6} sau {2, 3, 5, 6}.
Rezolvare:
Soluţia problemei nu este unică, dar lungimea maximă a subşirului crescător, da.
Vom nota cu L[k] lungimea celui mai lung subşir crescător care începe de la poziţia k şi până la sfârşitul şirului iniţial. Calculăm, pe rând, L[n], L[n-1], L[n-2] … L[2], L[1]. Lungimea celui mai lung subşir crescător va fi dată de cea mai mare valoare a lui L.
L[n] = 1
L[k] = 1+ max {L[i ], unde k
#include
int v[10000],n,i,L[1000],max,mx,k,t;
void main(){
fstream f(“subsir.txt”,ios::in);
for(i=1;i<=n;i++) f>>v[i];
L[n]=1; subsir maxim de lung 1
for(k=n-1;k>0;k–)
{mx=0;
for(i=k+1;i<=n;i++)
if(v[i]>=v[k] && L[i]>mx)
mx=L[i];
L[k]=mx+1;
if(L[k]>max)
{max=L[k];
t=k;}
}
cout<<“lungimea maxima:”<
cout<
for(i=t+1;i<=n;i++)
if ((v[i]>=v[t]) && (L[i]==max-1))
{cout<
max–;}
}
2. Subşir comun maximal
Fie X=(x1, x2, …, xn) şi Y=(y1, y2, …, ym) două şiruri de n, respectiv m numere întregi. Determinaţi un subşir comun de lungime maximă.
Exemplu
Pentru X=(2,5,5,6,2,8,4,0,1,3,5,8) şi Y=(6,2,5,6,5,5,4,3,5,8) o soluţie posibilă este: Z=(2,5,5,4,3,5,8)
Rezolvare:
Notăm cu Xk=(x1, x2, …, xk) (prefixul lui X de lungime k) şi cu Yh=(y1, y2, …, yh) prefixul lui Y de lungime h. O subproblemă a problemei date constă în determinarea celui mai lung subşir comun al lui Xk, Yh. Notăm cu LCS(k,h) lungimea celui mai lung subşir comun al lui Xk, Yh. Utilizând aceste notaţii, problema cere determinarea LCS(n,m), precum şi un astfel de subşir.
Pentru a reţine soluţiile subproblemelor vom utiliza o matrice cu n+1 linii şi m+1 coloane, denumită LCS. Linia şi coloana 0 sunt iniţializate cu 0, iar elementul LCS[k][h] va fi lungimea celui mai lung subşir comun al şirurilor Xk şi Yh.
Vom caracteriza substructura optimală a problemei prin următoarea relaţie de recurenţă:
lcs[k][0]=lcs[0][h]=0, k din {1,2,..,n}, h din {1,2,..,m}
lcs[k][h]=1+lcs[k-1][h-1], dacă x[k]=y[h]
max{lcs[k][h-1], lcs[k-1][h]}, dacă x[k]<>y[h]
#include
int x[100],y[100],n,m;
int lcs[100][100],max;
void rezolva(){
for(int k=1;k<=n;k++)
for(int h=1;h<=m;h++)
if(x[k]==y[h]) lcs[k][h]=1+lcs[k-1][h-1];
else
if (lcs[k-1][h]>lcs[k][h-1]) lcs[k][h]=lcs[k-1][h];
else lcs[k][h]=lcs[k][h-1];
}
void afiseaza_solutie_max(int k,int h){
if(lcs[k][h])
if(x[k]==y[h])
{afiseaza_solutie_max(k-1,h-1);
cout<
else
{if (lcs[k][h]==lcs[k-1][h])
afiseaza_solutie_max(k-1,h);
else if (lcs[k][h]==lcs[k][h-1])
afiseaza_solutie_max(k,h-1);
}
}
void main(){
ifstream f(“lcs.txt”,ios::in);
f>>n>>m;
for(int i=1;i<=n;i++) f>>x[i];
for(i=1;i<=m;i++) f>>y[i];
rezolva();
afiseaza_solutie_max(n,m);
}
3. Sumă maximă în triunghi
Fie triunghiul format din n linii (1
 |
| Image |
Determinaţi cea mai mare sumă de numere aflate pe un drum între numărul de pe prima linie şi un număr de pe ultima linie. Fiecare număr din acest drum este situat sub precedentul, la stânga sau la dreapta acestuia.
Rezolvare
1. Vom reţine triunghiul într-o matrice pătratică T, de ordin n, sub diagonala principală. Subproblemele problemei date constau în determinarea sumei maxime care se poate obţine din numere aflate pe un drum între numărul T[i ][j], până la un număr de pe ultima linie, fiecare număr din acest drum fiind situat sub precedentul, la stânga sau la dreapta sa. Evident, subproblemele nu sunt independente: pentru a calcula suma maximă a numerelor de pe un drum de la T[i ][j] la ultima linie, trebuie să calculăm suma maximă a numerelor de pe un drum de la T[i+1][j] la ultima linie şi suma maximă a numerelor de pe un drum de la T[i+1][j+1] la ultima linie.
2. Pentru a reţine soluţiile subproblemelor, vom utiliza o matrice suplimentară S, pătratică de ordin n, cu semnificaţia
S[i ][j]= suma maximă ce se poate obţine pe un drum de la T[i ][j] la un element de pe ultima linie, respectând condiţiile problemei.
Soluţia problemei va fi S[1][1].
3. Relaţia de recurenţă care caracterizează substructura optimală a problemei este:
S[n][ i]=T[n][i ], i din {1,2,…,n}
S[i ][j]=T[i ][j]+max{S[i+1][j], S[i+1][j+1]}
Secvenţa de program este:
for (i=1; i<=n; i++) S[n][i]=T[n][i];
for (i=n-1; i>=1; i–)
for (j=1; j<=i; j++)
{if (S[i+1][j]
else
S[i][j]=T[i][j]+S[i+1][j];}
SUMATRI.cpp
PROBLEME PROPUSE
1. Împărţirea unei mulţimi în 2 submulţimi de sume cât mai apropiate
La sfarsitul noptii de Craciun, Mosul a poposit la bradul a doi frati, unde si-a golit sacul. Cand s-au trezit, fratii au intrat intr-o mare dilema: cum isi vor imparti ei cadourile mosului? Stiind ca fiecare cadou are o valoare (cuprinsa intre 1 si 100 inclusiv) si ca sunt maxim 100 de cadouri scrieti un program care sa determine sumele cadourilor fratilor, precum si modul de impartire, astfel incat sumele obtinute sa fie cele mai apropiate posibil.
Date de intrare:
In fisierul CADOURI.IN se gasesc informaţiile referitoare la cadouri: pe prima linie numarul total de cadouri, pe urmatoarea linie valorile lor.
Date de iesire: In fişierul CADOURI.OUT trebuie scrise doua sume care sunt cele mai apropiate corespunzătoare unei impartiri a cadourilor, pe a doua linie valorile corespunzătoare cadourilor care însumează prima suma găsită, pe a treia linie, valorile corespunzătoare cadourilor care însumează a doua suma găsită.
Exemplu:
CADOURI.IN CADOURI.OUT
7 48 49
28 7 11 8 9 7 27 28 11 9
7 8 7 27
2. Sumă maximă
Se consideră un şir de N (N£1000) numere naturale cuprinse între 1 şi 10.000. Să se determine o sumă maximă de componente ale şirului astfel încât în sumă să nu intre două numere care se află pe poziţii consecutive în şir.
Exemplu: pentru şirul 1 10 2 40 100, suma maximă este 110 (10+100)