Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-12-05 14:35:20.
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 doua articole: PD basic si PD advanced
  • cred ca era si ceva prin Cartea lui Francu' despre programare dinamica; ar merge incorporat (eventual in pd_basic).

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 ...