0/1-Rucksack und Speicheroptimierung

Das 0/1-Rucksackproblem: Gegeben seien n Gegenstände, jeweils mit einem Gewicht w[i] und einem Wert v[i], sowie ein Rucksack mit der Kapazität W. Wählen Sie Gegenstände aus, um den Gesamtwert zu maximieren, ohne die Kapazität zu überschreiten. Jeder Gegenstand wird genau einmal berücksichtigt (0 = überspringen, 1 = nehmen). Dies ist das archetypische Beispiel für eine große Familie von DP-Aufgaben in Vorstellungsgesprächen, einschließlich der Probleme Partition Equal Subset Sum und Target Sum.

Definieren Sie dp[i][c] als den maximalen Wert, der mit den ersten i Gegenständen und der Kapazität c erzielt werden kann. Für Gegenstand i gibt es zwei Möglichkeiten: ihn überspringen (dp[i-1][c]) oder ihn nehmen, wenn w[i] <= c gilt (dp[i-1][c-w[i]] + v[i]). Die Rekurrenz lautet: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]), wenn w[i] <= c gilt, andernfalls dp[i][c] = dp[i-1][c]. Basisfall: dp[0][c] = 0 für alle c.

Die 2D-Tabelle enthält (n+1) x (W+1) Einträge und wird für jeden Gegenstand zeilenweise gefüllt. Nach dem Füllen aller Zeilen enthält dp[n][W] den maximalen Wert. Die Laufzeit beträgt O(n × W) und der Speicherbedarf O(n × W) — eine pseudopolynomiale Komplexität, die effizient ist, wenn W klein ist.

Die entscheidende Beobachtung: Zeile i hängt nur von Zeile i-1 ab. Daher können wir ein einziges 1D-Array verwenden und es direkt aktualisieren. Wenn wir die Kapazität c jedoch von links nach rechts durchlaufen (von klein nach groß), wird Gegenstand i möglicherweise doppelt gezählt — wir könnten den bereits aktualisierten Wert für c-w[i] verwenden, der Gegenstand i schon enthält. Das Durchlaufen von rechts nach links (von groß nach klein) stellt sicher, dass jeder Gegenstand bei einer Zeilenaktualisierung höchstens einmal verwendet wird.

Indem wir nur ein Array beibehalten und die Kapazität von W abwärts bis w[i] durchlaufen, erzielen wir dasselbe Ergebnis wie mit der 2D-Tabelle bei einem Speicherbedarf von O(W). Die Zeitkomplexität bleibt O(n × W). Diese Speicheroptimierung sollten Sie sich unbedingt merken — in Vorstellungsgesprächen werden Sie häufig aufgefordert, den 2D-Rucksack auf 1D zu reduzieren.

Um herauszufinden, welche Gegenstände ausgewählt wurden, benötigen Sie die vollständige 2D-Tabelle. Beginnen Sie nach dem Füllen bei dp[n][W] und gehen Sie rückwärts vor: Wenn dp[i][c] != dp[i-1][c] gilt, wurde Gegenstand i ausgewählt — ziehen Sie sein Gewicht von c ab und wechseln Sie in Zeile i-1. Fahren Sie fort, bis i = 0 gilt. Die 1D-Optimierung verwirft diese Möglichkeit zur Rekonstruktion.

Betrachten Sie die Gegenstände: weights=[2,3,4,5], values=[3,4,5,6], W=8. Optimal ist die Auswahl der Gegenstände mit Gewicht 3 (Wert 4) und Gewicht 5 (Wert 6) — Gesamtgewicht 8, Wert 10. Oder Sie wählen die Gewichte 2 und 5 — Gesamtwert 9. Oder die Gewichte 2 und 3 — Wert 7. Die DP findet korrekt das Maximum 10. Beachten Sie, dass der Greedy-Ansatz (Auswahl nach dem höchsten Wert-Gewicht-Verhältnis) zuerst den Gegenstand mit dem Verhältnis 1.5 wählen würde (Gewicht 2, Wert 3) — was nicht immer optimal ist.

Beim fraktionalen Rucksackproblem können Sie Bruchteile von Gegenständen nehmen. Dieses Problem lässt sich gierig lösen, indem nach dem Wert-Gewicht-Verhältnis sortiert wird. Beim 0/1-Rucksackproblem sind die Gegenstände unteilbar — ein Greedy-Ansatz scheitert, DP ist erforderlich. Interviewer nutzen diese Unterscheidung, um zu prüfen, ob Sie wissen, wann Greedy anwendbar ist. Wenn Sie nach der fraktionalen Variante gefragt werden, erwähnen Sie sofort Greedy mit Sortierung; bei 0/1 greifen Sie zu DP.

Das 0/1-Rucksackproblem ist NP-vollständig, dennoch lösen wir es in O(nW) Zeit. Der scheinbare Widerspruch löst sich auf, weil O(nW) pseudopolynomial ist: W ist ein Wert und nicht die Eingabegröße. Die binäre Darstellung von W benötigt O(log W) Bits, daher ist die tatsächliche Komplexität O(n × 2^(log W)) und damit exponentiell bezüglich der Eingabegröße. Wenn W klein ist (z. B. 10⁴), ist die DP praktikabel; wenn W bis zu 10⁹ groß werden kann, benötigen wir andere Ansätze.

Wenn der Interviewer W sehr groß vorgibt (z. B. 10⁹), aber n klein ist, funktioniert die standardmäßige DP nicht mehr. Alternativen sind: (1) Meet-in-the-Middle mit einer Laufzeit von O(2^(n/2) × n), (2) eine Greedy-Approximation für die fraktionale Variante oder (3) Branch-and-Bound. Für die meisten Aufgaben in Vorstellungsgesprächen mit W <= 10⁵ ist die 1D-DP mit Rückwärtsdurchlauf die erwartete Lösung.

Wenn W sehr groß, aber n klein ist (z. B. n=40), ist die standardmäßige O(nW)-DP nicht praktikabel, während vollständiges Durchprobieren von 2^n zu langsam ist. Meet-in-the-Middle teilt die Gegenstände in zwei Hälften, erzeugt für jede Hälfte alle 2^(n/2) Teilmengen und kombiniert sie optimal. Sortieren Sie eine Hälfte nach Gewicht und verwenden Sie dann für jede Teilmenge der anderen Hälfte die binäre Suche, um die beste Kombination innerhalb der Kapazität zu finden. Die Laufzeit beträgt O(2^(n/2) × n) — praktikabel für n bis 40.

Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.

In dieser Lektion haben Sie gelernt: Die 0/1-Rucksack-DP verwendet den Zustand dp[i][c], der den maximalen Wert mit i Gegenständen und der Kapazität c darstellt, die Rekurrenz wählt für jeden Gegenstand zwischen Überspringen und Nehmen, und die 1D-Speicheroptimierung durchläuft die Kapazität von rechts nach links, um das doppelte Zählen von Gegenständen zu verhindern. Als Nächstes untersuchen wir das unbeschränkte Rucksackproblem, bei dem Gegenstände wiederverwendet werden können, und wenden es auf Coin Change II an.