De ce contează?
Ești un hoț cu un rucsac care duce cel mult 5 kilograme. În fața ta sunt patru obiecte de furat, fiecare cu greutatea și valoarea lui. Nu poți lua jumătate de obiect — fie îl iei întreg, fie îl lași. Întrebarea care îți decide prada: ce combinație îți aduce cea mai mare valoare fără să rupi rucsacul?
Intuiția
Multe probleme de concurs cer un maxim sau un minim sub o constrângere: „cea mai mare valoare cu greutate cel mult W", „costul minim până la destinație". Programarea dinamică le rezolvă punând o singură întrebare pentru fiecare element: îl iau sau nu? Dacă reții, pentru fiecare capacitate posibilă, cea mai bună valoare obținută până acum, fiecare obiect nou doar îmbunătățește acel tabel.
Exemplul canonic este rucsacul 0/1 (knapsack): obiecte cu greutate și valoare, o capacitate W, iar tu maximizezi valoarea fără să depășești W.