Informatică Algoritmi
Programare dinamica exemple rezolvate
Programarea dinamică este o metodă de rezolvare a problemelor complexe prin descompunerea lor în subprobleme mai mici, ale căror soluții sunt stocate și reutilizate pentru a evita calculele repetate. Această tehnică asigură eficiență în timp și memorie, fiind ideală pentru probleme de optimizare cu suprapuneri. Exemplu clasic: calculul termenilor din șirul lui Fibonacci.
Exemplu 1: Șirul lui Fibonacci
- 1 Pasul 1: Definirea subproblemelor Fie F(n) al n-lea termen Fibonacci; F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) pentru n≥2.
- 2 Pasul 2: Stocarea rezultatelor Folosește un vector fib[] pentru a memora valorile calculate: fib[0]=0, fib[1]=1.
- 3 Pasul 3: Calcul iterativ Pentru i de la 2 la n: fib[i]=fib[i-1]+fib[i-2]; evită recalcularea termenilor anteriori.
- 4 Pasul 4: Rezultat final fib[n] dă valoarea dorită; complexitate O(n) față de O(2^n) la abordarea recursivă naivă.
Exemplu 2: Problema rucsacului 0-1
- 1 Pasul 1: Definirea variabilelor Avem n obiecte cu greutăți w[i] și valori v[i], capacitate maximă W; dp[i][j] = valoarea maximă cu primele i obiecte și greutate j.
- 2 Pasul 2: Inițializare dp[0][j]=0 pentru toate j (niciun obiect); dp[i][0]=0 pentru toate i (greutate 0).
- 3 Pasul 3: Relația de recurență Pentru fiecare obiect i și greutate j: dacă w[i]≤j, dp[i][j]=max(dp[i-1][j], v[i]+dp[i-1][j-w[i]]); altfel dp[i][j]=dp[i-1][j].
- 4 Pasul 4: Rezolvare Calculează dp[n][W]; exemplu numeric: n=3, w=[2,3,4], v=[3,4,5], W=5 → dp[3][5]=7 (obiectele 1 și 2).
Aplică programarea dinamică pentru probleme cu subprobleme suprapuse; memorează rezultatele într-un tabel pentru eficiență.