Overview
0/1 Rucksackproblem: Gegenstände mit Gewicht und Wert, Gesamtwert maximieren ohne Kapazität zu überschreiten.
Analogy
Koffer packen für eine Reise: jeden Gegenstand höchstens einmal mitnehmen; Gesamtgewicht begrenzt.
Step-by-step
- dp[i][w] = maximaler Wert mit ersten i Gegenständen und Kapazität w.
- Für jeden Gegenstand i: für w=0..W. Wenn w<weight[i]: dp[i][w]=dp[i-1][w]. Sonst: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]).
- Antwort ist dp[n][W].
Visual
Gegenstände [(2,3),(3,4),(4,5)] W=5 → dp-Tabelle → Maxwert=7 (Gegenstände 0+1)
Common mistakes
- 1D-Array vorwärts iterieren (muss rückwärts für 0/1 Rucksack).
- dp[i-1]-Zeile vergessen zu kopieren bei 1D-Optimierung.
Practice questions
- Gewählte Gegenstände durch Rückverfolgung der dp-Tabelle rekonstruieren.
- Teilmengensumme lösen (Wert=Gewicht, Ziel=W).
Space
O(W) mit 1D-Optimierung