(Categoria _Tehnici de programare_, autori _Catalin Tiseanu_, _Andrei Homescu_)

TODO:

TODO://ok..to do...dar do mai repede...k e foarte bun articolul si vreau sa citesc si partea cealalta...e pacat sa lasati articolul neterminat asa...vede lumea...bine..e si funny ;)) peace out ;)

1. Reparat link de la ugly numbers

h2. Programare dinamică folosind măşti de biţi şi codificări $k$-are

Unele probleme de programare dinamica au drept componentă a stării unei subprobleme o mulţime de elemente care fac parte din subproblemă. Astfel, subproblema nu este o reducere a problemei iniţiale la un subset continuu de elemente ($1..i$ sau $i..j$) ci la un subset oarecare. În acest caz, codificăm submulţimea curentă în stare, ca vector sau ca număr întreg. Dacă dimensiunea submulţimii este suficient de mic putem folosi un întreg pentru a codifica această informaţie astfel:

Unele probleme de programare dinamica au drept componentă a stării unei subprobleme o mulţime de elemente care fac parte din subproblemă. Astfel, subproblema nu este o reducere a problemei iniţiale la un subset continuu de elemente ({$1..i$} sau $i..j$) ci la un subset oarecare. În acest caz, codificăm submulţimea curentă în stare, ca vector sau ca număr întreg. Dacă dimensiunea submulţimii este suficient de mic putem folosi un întreg pentru a codifica această informaţie astfel:

Fie mulţimea $A$ = { x{~1~}, x{~2~}, ... x{~n~} }.

Atunci masca de biţi a unei partitii a lui $A, $MASK$, va avea bitul $i$ egal cu 1 dacă şi numai dacă x{~i~} apartine partitiei. Desigur, această reprezentare duce la o complexitate direct proporţională cu $2 ^card(A)^$. Putem intui dacă trebuie să folosim o astfel de rezolvare din limitele valorilor de intrare; pentru $N$ cu valori cuprinse între $10-20$, deducem că trebuie să căutăm o astfel de soluţie.

Atunci masca de biţi a unei partitii a lui $A$, $MASK$, va avea bitul $i$ egal cu 1 dacă şi numai dacă x{~i~} apartine partitiei. Desigur, această reprezentare duce la o complexitate direct proporţională cu $2 ^card(A)^$. Putem intui dacă trebuie să folosim o astfel de rezolvare din limitele valorilor de intrare; pentru $N$ cu valori cuprinse între $10-20$, deducem că trebuie să căutăm o astfel de soluţie.

Pentru multe probleme, fiecare element poate face parte din subproblemă în mai mult de 2 feluri. De exemplu, dacă starea reprezintă o linie de maxim $K$ elemente dintr-o matrice iar fiecare element de pe linie poate avea valorile 0, 1 sau 2 atunci există $3^K$ variante distincte posibile pentru o astfel de linie. Un alt exemplu este o problemă de optimizare în care fiecare element (participant) se poate afla în una din câteva stări (dacă $N$ persoane trebuie să treacă un pod peste un râu, cele 3 stări pot fi: _pe malul stâng_, _pe pod_ şi _pe malul drept_).