Pe scurt
Algoritmii greedy și programarea dinamică sunt două paradigme fundamentale pentru probleme de optimizare, frecvent testate la bacalaureat. Greedy face alegeri locale optime ireversibile, fiind rapid dar corect doar pentru anumite probleme, în timp ce DP descompune problema în subprobleme suprapuse și stochează rezultatele intermediare, garantând soluția optimă. Diferența esențială constă în faptul că greedy este mai eficient ca timp, dar poate eșua, pe când DP este corect, dar consumă mai multă memorie.
Ce sunt algoritmii greedy și programarea dinamică?
Algoritmii greedy (lacomi) și programarea dinamică sunt două paradigme fundamentale în rezolvarea problemelor de optimizare, frecvent întâlnite la examenul de bacalaureat la informatică (clasele 9-12, profil real).
Algoritmul greedy
- Face alegeri locale optime la fiecare pas, sperând că acestea vor duce la o soluție globală optimă.
- Este rapid și ușor de implementat, dar funcționează corect doar dacă problema are proprietatea de substructură optimală și alegerea locală este sigură.
- Ia decizii ireversibile bazate pe o euristică locală.
- Este valid doar pentru anumite probleme (ex: rucsac fracționar, arbore parțial de cost minim, coduri Huffman).
Programarea dinamică (DP)
- Rezolvă probleme prin descompunerea lor în subprobleme mai mici, stocând rezultatele intermediare pentru a evita recalcularea.
- Este potrivită pentru probleme unde soluția optimă conține soluții optime ale subproblemelor (principiul optimalității lui Bellman).
- Explorează sistematic toate opțiunile, dar eficient.
- Aplicabilă la probleme de numărare, optimizare (ex: Fibonacci, LCS, rucsac 0/1, probleme de drum minim).
Diferența cheie între greedy și DP
- Greedy este mai rapid (O(n log n) de obicei) dar nu întotdeauna corect.
- DP este corect dar consumă mai multă memorie (O(n²) sau mai mult) și timp, însă garantează soluția optimă.
Exemple clasice
Exemplul 1 (Greedy): Plata unei sume cu număr minim de bancnote
- Se dă suma S=173 și bancnote disponibile: 100, 50, 10, 5, 1.
- Algoritmul greedy: ia cea mai mare bancnotă ≤ suma rămasă.
- 173 → 1x100 (rest 73)
- → 1x50 (rest 23)
- → 2x10 (rest 3)
- → 3x1 (rest 0)
- Rezultat: 1+1+2+3=7 bancnote.
- Este optim deoarece bancnotele sunt standard (fiecare este multiplu al precedentei).
Exemplul 2 (DP): Numărul de moduri de a urca n scări
- Se pot urca 1 sau 2 trepte odată, pentru n=4.
- Notăm dp[i] = nr. moduri de a ajunge pe treapta i.
- Recurența: dp[0]=1 (bază), dp[1]=1, dp[i]=dp[i-1]+dp[i-2].
- Calcul:
- dp[2]=dp[1]+dp[0]=1+1=2
- dp[3]=dp[2]+dp[1]=2+1=3
- dp[4]=dp[3]+dp[2]=3+2=5
Exemplul 3 (DP): Cel mai lung subșir comun (LCS)
- Între șirurile X=ABCBDAB și Y=BDCABA.
- Se construiește o matrice dp de dimensiune (m+1)x(n+1).
- Inițial pe prima linie și coloană 0.
- Pentru fiecare i,j:
- Dacă
X[i]==Y[j] atunci
dp[i][j]=dp[i-1][j-1]+1
- Altfel dp[i][j]=max(dp[i-1][j], dp[i][j-1])
- Rezultatul dp[7][6]=4 (subșirul 'BDAB' sau 'BCAB').
Cum abordezi problemele la bac
- Citește enunțul cu atenție.
- Identifică dacă se cere 'număr maxim/minim de ...'.
- Verifică dacă alegerea locală optimă duce la soluția globală (greedy) sau dacă trebuie să încerci toate combinațiile (DP).
- Exersează implementările de bază: sortare + selecție pentru greedy, și tabla 2D pentru DP.
- Notă: la bac, codul sursă se scrie în pseudocod sau limbaj C/C++ (conform cerinței).
Capcane frecvente
- O capcană frecventă este să aplici greedy acolo unde nu e valid (de exemplu, la rucsac cu obiecte fracționare e ok, dar la rucsac 0/1 nu merge întotdeauna).
Verifică-te!
- Care este diferența fundamentală între modul în care un algoritm greedy și programarea dinamică iau deciziile?
- În exemplul cu plata sumei de 173 lei, de ce funcționează corect algoritmul greedy?
- Ce proprietate trebuie să aibă o problemă pentru a putea fi rezolvată corect prin programare dinamică?