Revizia anterioară Revizia următoare
Programare dinamica
(Categoria Tehnici de programare, autor Catalin Tiseanu)
Plan de atac (probleme-candidat):
1. http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en
2. http://code.google.com/codejam/contest/dashboard?c=32001#s=p0&a=3
3. http://code.google.com/codejam/contest/dashboard?c=32001#s=p3&a=3
4. http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1
5. http://code.google.com/codejam/contest/dashboard?c=32010#s=p3&a=3
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
Programarea dinamica este o metoda utila pentru a rezolva probleme care pot fi obtinute prin compunerea a mai multor bucati, a caror solutie poate fi apoi determinata optim. Se bazeaza in principal pe proprietatea unei probleme de a putea fi rezolvata optim daca se cunosc solutii optime la sub-problemele ei.
De mentionat ca 'programare' nu se refera aici la scrierea de cod intr-un limbaj de programare, si la 'programare matematica', care consta in optimizarea unei functii prin alegerea de valori dintr-un multime anume.
Scopul acestui articol nu este sa ofere o introducere in programare dinamica (pentru aceasta poate fi consultat excelentul tutorial de pe TopCoder 'Dynamic Programming: From novice to advanced' http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg). In schimb, acest articol isi propune sa ofere niste 'smenuri' mai avansate de rezolvare a problemelor cu programare dinamica,
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 ...
