Programare dinamica (probleme clasice: rucsac, subsir comun maximal)

Pe scurt

Programarea dinamică optimizează algoritmii prin descompunerea problemei în subprobleme mai mici, ale căror soluții sunt calculate o singură dată și reutilizate. Cele două probleme clasice sunt problema rucsacului (maximizarea valorii obiectelor într-o capacitate dată) și subșirul comun maximal (determinarea celui mai lung subșir comun a două șiruri). Tehnica reduce complexitatea de la exponențială la polinomială, utilizând proprietățile de substructură optimală și suprapunere a subproblemelor.

Proprietăți și principii de bază

• Substructură optimală: Soluția optimă globală conține soluțiile optime ale subproblemelor
• Suprapunerea subproblemelor: Aceleași subprobleme apar de mai multe ori în procesul de rezolvare
• Memoizare: Stocarea rezultatelor subproblemelor pentru reutilizare
• Abordare iterativă (bottom-up): Construcția soluției de la subprobleme mici la problema mare

Problema rucsacului (Knapsack 0/1)

Descrierea problemei

• Avem n obiecte, fiecare cu greutatea w[i] și valoarea v[i]
• Rucsacul are capacitatea G
• Scopul: maximizarea valorii totale a obiectelor selectate fără a depăși greutatea G

Rezolvarea dinamică

• Se folosește o matrice dp[i][j] = valoarea maximă obținută folosind primele i obiecte și o greutate totală de exact j (sau maxim j)
• Relația de recurență:

- Dacă j ≥ w[i]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

- Altfel: dp[i][j] = dp[i-1][j]

• Optimizarea memoriei: Se poate reduce la un vector pe dimensiunea G, iterând greutatea descrescător pentru a evita reutilizarea aceluiași obiect

Exemplu practic

• Capacitate G=10, 4 obiecte: (w=5, v=10), (w=4, v=40), (w=6, v=30), (w=3, v=50)
• Se construiește matricea dp cu 5 linii (0..4) și 11 coloane (0..10)
• Inițializăm linia 0 cu 0
• Pentru i=1 (obiect 5,10): pentru j=0..4 dp=0, j=5..10 dp=10
• Pentru i=2 (4,40): j=4..9 max(dp[1][j], dp[1][j-4]+40) – dp[2][4]=40, dp[2][9]=50
• Pentru i=3 (6,30): j=6..10 compară – dp[3][6]=max(40,0+30)=40, dp[3][10]=max(50, dp[2][4]+30=70)
• Pentru i=4 (3,50): j=3..10 – dp[4][3]=50, dp[4][7]=max(40, dp[3][4]+50=90), dp[4][10]=max(70, dp[3][7]+50=90)
• Răspuns: valoare maximă = 90, cu obiectele 2 (4,40) și 4 (3,50) – greutate 7, valoare 90

Subșirul comun maximal (LCS)

Descrierea problemei

• Se dau două șiruri: A (lungime m) și B (lungime n)
• Se cere lungimea celui mai lung subșir care apare în ambele șiruri, fără a fi neapărat consecutiv

Rezolvarea dinamică

• Matricea dp[i][j] reprezintă lungimea LCS pentru prefixele A[1..i] și B[1..j]
• Relația de recurență:

- Dacă A[i] == B[j]: dp[i][j] = dp[i-1][j-1] + 1

- Altfel: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

• Inițializarea: dp[0][j] = 0, dp[i][0] = 0
• Reconstituirea soluției: Se parcurge matricea invers, urmărind direcția din care provine valoarea

Exemplu practic

• Șirurile: A = 'ABCBDAB', B = 'BDCABA'
• Se construiește matricea dp (m+1)x(n+1), inițializare cu 0
• Pentru i=1 (A[1]='A'), j=1 (B[1]='B'): diferit, dp[1][1]=max(0,0)=0
• j=2 ('D'): 0; j=3 ('C'):0; j=4 ('A'): egal, dp[1][4]=dp[0][3]+1=1; j=5 ('B'): 0; j=6 ('A'): egal, dp[1][6]=dp[0][5]+1=1
• Se obține dp[7][6] = 4
• Reconstituire: Pornim de la (7,6), valorile egale duc la diagonala când caracterele coincid
• LCS = 'BCAB' sau 'BCBA' – lungime 4

Optimizări și aplicații

Optimizarea memoriei pentru rucsac

• Se folosește un vector unidimensional în loc de matrice
• Se iterează greutatea descrescător pentru a evita reutilizarea aceluiași obiect
• Pentru reconstituire, se păstrează o matrice sau se verifică dp în ordine inversă

Complexități

• Rucsac: O(n*G)
• LCS: O(m*n)

Aplicații practice

• Planificare și optimizare resurse
• Bioinformatică (alinierea secvențelor)
• Compresia datelor

Limitări

• Problemele cu greutăți mari sau șiruri foarte lungi pot necesita optimizări suplimentare
• La bacalaureat se cere implementarea corectă a recurenței și determinarea valorii optime, uneori și reconstituirea soluției

Verifică-te!

1. Care sunt cele două proprietăți pe care trebuie să le îndeplinească o problemă pentru a putea fi rezolvată prin programare dinamică?

1. În problema rucsacului 0/1, de ce trebuie să iterăm greutatea descrescător atunci când optimizăm memoria la un vector unidimensional?

1. Care este relația de recurență pentru subșirul comun maximal (LCS) atunci când caracterele A[i] și B[j] sunt diferite?