Metoda Programării Dinamice în Programare 4
1. Obiectivele lecției:
- Să înțeleagă conceptul metodei Programării Dinamice.
- Să învețe cum să rezolve probleme complexe folosind subprobleme suprapuse.
- Să implementeze exemple practice care folosesc această metodă.
2. Ce este Programarea Dinamică?
- Definiție:
Programarea Dinamică (Dynamic Programming – DP) este o metodă de optimizare care rezolvă probleme complexe prin împărțirea acestora în subprobleme mai mici și memorarea soluțiilor intermediare pentru a evita recalcularea lor. - Cerințe pentru aplicarea metodei:
- Subprobleme suprapuse: Problemele mai mari pot fi împărțite în subprobleme care se repetă.
- Substructură optimă: Soluția optimă a unei probleme poate fi construită din soluțiile optime ale subproblemelor.
- Tehnici de implementare:
- Top-Down (Memoization): Soluția este calculată recursiv, iar rezultatele intermediare sunt memorate.
- Bottom-Up (Tabulation): Se construiește soluția într-un mod iterativ, pornind de la cele mai mici subprobleme.
3. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Reduce recalculările prin memorarea soluțiilor. | Necesită mai multă memorie pentru stocarea intermediară. |
| Garantează o soluție optimă, dacă există. | Poate fi dificil de implementat pentru probleme complexe. |
| Eficient pentru probleme care au subprobleme repetate. | Necesită identificarea clară a subproblemelor. |
4. Probleme rezolvate prin Programare Dinamică
- Fibonacci.
- Problema rucsacului (Knapsack problem).
- Cel mai lung subșir comun (Longest Common Subsequence – LCS).
- Număr de drumuri într-o matrice.
- Problema sumei parțiale.
5. Etapele metodei
- Formularea problemei:
Identificați cum poate fi împărțită problema principală în subprobleme mai mici. - Definirea stării:
Definește starea problemei ca o relație recurentă (dp[i]dp[i]dp[i], dp[i][j]dp[i][j]dp[i][j], etc.). - Relația de recurență:
Scrieți relația care definește cum se construiește soluția din subproblemele anterioare. - Cazul de bază:
Definește condițiile inițiale pentru algoritm. - Implementarea algoritmului:
Implementați metoda folosind tehnici top-down sau bottom-up.
6. Exemple practice
Exemplu 1: Numerele Fibonacci
- Problema:
Calculați al nnn-lea număr din șirul Fibonacci. - Relația de recurență:
F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)
cu F(0)=0F(0) = 0F(0)=0 și F(1)=1F(1) = 1F(1)=1.
- Implementare Bottom-Up:
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1) return n;
int dp[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i – 1] + dp[i – 2];
}
return dp[n];
}
int main() {
int n = 10;
cout << „Fibonacci(” << n << „) = ” << fibonacci(n) << endl;
return 0;
}
Exemplu 2: Problema rucsacului (Knapsack Problem)
- Problema:
Avem un rucsac cu o capacitate WWW și nnn obiecte, fiecare cu o greutate w[i]w[i]w[i] și o valoare v[i]v[i]v[i]. Găsiți valoarea maximă care poate fi transportată. - Relația de recurență:
dp[i][w]=max(dp[i−1][w],v[i]+dp[i−1][w−w[i]])dp[i][w] = \max(dp[i-1][w], v[i] + dp[i-1][w-w[i]])dp[i][w]=max(dp[i−1][w],v[i]+dp[i−1][w−w[i]])
- Implementare Bottom-Up:
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& greutati, vector<int>& valori, int n) {
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (greutati[i – 1] <= w) {
dp[i][w] = max(dp[i – 1][w], valori[i – 1] + dp[i – 1][w – greutati[i – 1]]);
} else {
dp[i][w] = dp[i – 1][w];
}
}
}
return dp[n][W];
}
int main() {
vector<int> greutati = {1, 2, 3};
vector<int> valori = {10, 15, 40};
int W = 6;
cout << „Valoarea maximă: ” << knapsack(W, greutati, valori, greutati.size()) << endl;
return 0;
}
Exemplu 3: Cel mai lung subșir comun (Longest Common Subsequence – LCS)
- Problema:
Găsiți lungimea celui mai lung subșir comun între două șiruri. - Relația de recurență:
dp[i][j]={dp[i−1][j−1]+1,daca˘ s1[i]==s2[j]max(dp[i−1][j],dp[i][j−1]),altfeldp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{dacă } s1[i] == s2[j] \\ \max(dp[i-1][j], dp[i][j-1]), & \text{altfel} \end{cases}dp[i][j]={dp[i−1][j−1]+1,max(dp[i−1][j],dp[i][j−1]),daca˘ s1[i]==s2[j]altfel
- Implementare Bottom-Up:
#include <iostream>
#include <vector>
using namespace std;
int lcs(string s1, string s2) {
int n = s1.size(), m = s2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i – 1] == s2[j – 1]) {
dp[i][j] = dp[i – 1][j – 1] + 1;
} else {
dp[i][j] = max(dp[i – 1][j], dp[i][j – 1]);
}
}
}
return dp[n][m];
}
int main() {
string s1 = „ABCBDAB”;
string s2 = „BDCAB”;
cout << „Lungimea celui mai lung subșir comun: ” << lcs(s1, s2) << endl;
return 0;
}
7. Activități practice pentru elevi
- Implementați un algoritm DP pentru a calcula numărul de drumuri posibile într-o matrice n×mn \times mn×m, pornind din colțul stânga-sus și terminând în colțul dreapta-jos.
- Scrieți un program care determină suma maximă a unui drum dintr-o matrice triunghiulară (Triangle Path Sum).
- Realizați un program DP care determină numărul de moduri de a face o sumă SSS utilizând un set de monede.
8. Scheme logice
- Flux Programare Dinamică:
- Start -> Definire stare -> Relație de recurență -> Construire soluție (Bottom-Up) -> Stop.
- Vizualizare LCS:
- Construirea unei matrice dp[i][j]dp[i][j]dp[i][j] pentru fiecare pereche de caractere.
9. Concluzie
- Programarea Dinamică este o metodă extrem de eficientă pentru probleme complexe cu subprobleme suprapuse.
- Memorarea soluțiilor intermediare reduce semnificativ timpul de execuție.
- Practica ajută la identificarea problemelor care pot fi rezolvate eficient prin această metodă.