Problema rucsacului 0/1
Pleci într-o drumeție cu un rucsac care duce cel mult 7 kg. Ai mai multe obiecte, fiecare cu o greutate și o valoare (cât de util îți este). Pe fiecare îl iei întreg sau deloc. Ce iei ca valoarea totală să fie maximă? Problema rucsacului 0/1 este modelul pentru zeci de probleme de interviu cu „buget limitat”.
Problema
Primești listele greutati și valori (obiectul i are greutatea greutati[i] și valoarea valori[i]) și capacitate. Alegi o submulțime de obiecte cu greutatea totală cel mult capacitate și valoarea totală maximă. Fiecare obiect se poate lua cel mult o dată (de aici „0/1”).
Scrie funcția rucsac(greutati, valori, capacitate) care returnează valoarea maximă a obiectelor care încap în rucsac (fiecare obiect cel mult o dată), cu programare dinamică. Testele sunt deja scrise.
- Creează un rând dp de lungime capacitate + 1, plin de 0.
- Pentru fiecare obiect, parcurge capacitățile **de la capacitate în jos până la greutatea obiectului**.
- Actualizează dp[c] = max(dp[c], dp[c - g] + v). Trebuie să apară: 9, 220, 3.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan