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 dinamică este o metodă utilă pentru a rezolva probleme care pot fi obţinute prin compunerea a mai multor bucăţi, a căror soluţie poate fi apoi determinată optim. Se bazează în principal pe proprietatea unei probleme de a putea fi rezolvată optim dacă se cunosc soluţii optime la sub-problemele ei.
De menţionat că 'programare' nu se referă aici la scrierea de cod într-un limbaj de programare, ci la 'programare matematica', care constă în optimizarea unei funcţii prin alegerea de valori dintr-o mulţime anume.
Scopul acestui articol nu este să ofere o introducere in programare dinamică (pentru aceasta poate fi consultat excelentul tutorial de pe TopCoder Dynamic Programming : From novice to advanced). În schimb, acest articol îşi propune să ofere nişte 'smenuri' mai avansate de rezolvare a problemelor cu programare dinamică.
Programare dinamică cu reducerea loop-ului interior
Să considerăm următoarea problema:
Problema 1: Drilling
Se da un şir de N numere naturale (a1, a2, ..., aN). Se ştie că un prefix al acestui şir (posibil chiar prefixul nul) este prost. Se ştie de asemenea că se poate testa orice poziţie i în timp ai dacă este proastă. Să se determine timpul minim în cazul cel mai defavorabil pentru aflarea lungimii maxime a prefixului şirului care este prost.
Exemplu:
Pentru secvenţa de numere (8 24 12 6), răspunsul ar fi (9, -2, 1, 7, 8).
Rezolvare:
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 ...
