Programare dinamica

(Categoria Tehnici de programare, autor Catalin Tiseanu)

Introducere

Problema introductiva

O aplicatie mai complicata

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 = { x₁, x₂, ... x_n }.
Atunci bitmaskul unei partitii a lui A, MASK, va avea bitul i egal cu 1 numai si numai daca x_i 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 ...