Revizia anterioară Revizia următoare
Programare dinamica
(Categoria Tehnici de programare, autor Catalin Tiseanu)
Sugestii Silviu
- poate ca nu trebuie sa spunem tot despre programare dinamica intr-un singur articol; spre exemplu putem facem un PD basic si un PD advanced
- numele paginii ar trebuie sa fie "programare_dinamica" si nu "pd";
Introducere
Cateva exemple "clasice"
Probleme avansate
Programare dinamica folosind bitmask
In continuare vom vedea un exemplu de programare dinamica unde vom folosi un bitmask (codificat pe un intreg) pentru a tine spatiul starilor.
Astfel sa presupunem ca avem nevoie sa tinem un vector caracteristic pentru o multime.
Daca cardinalul acesteia este suficient de mic putem folosi un intreg pentru a codifica aceasta informatie astfel:
Fie multimea A = { x1, x2, ... xn }.
Atunci bitmaskul unei partitii a lui A, MASK, va avea bitul i egal cu 1 numai si numai daca xi apartine partitiei.
Desigur, aceasta reprezentare duce la o complexitate direct proportionala cu 2 card(A).
Exemplu
Programare dinamica folosind vectori de numere intregi
To be continued ...