🎒 0/1-Rucksackproblem

Ausgehend von Zelle dp[n][W] vergleicht man sie mit dp[n−1][W]. Unterscheiden sie sich, wurde Gegenstand n einbezogen; sein Gewicht wird von W abgezogen, und man geht zu Zeile n−1. Sind sie gleich, wurde Gegenstand n ausgeschlossen; man geht zu dp[n−1][W]. Dies wird bis Zeile 0 wiederholt. Dieser Rückverfolgungsschritt läuft in O(n) Zeit.

Ja. Da dp[i][w] nur von Zeile i−1 abhängt, können zwei 1D-Arrays der Länge W+1 (aktuelle und vorherige Zeile) verwendet werden, was den Speicherbedarf auf O(W) reduziert. Iteriert man w in einem einzigen 1D-Array von W abwärts bis wᵢ, lässt sich O(W) Speicher in-place erreichen, ohne vorherige Zeilen zu speichern, wobei die Rückverfolgung dann eine Neuberechnung oder das Speichern von Zeilendifferenzen erfordert.

Branch-and-Bound durchsucht den exponentiellen Suchbaum der Einschluss-/Ausschluss-Entscheidungen, schneidet aber Teilbäume ab, deren obere Schranke (üblicherweise die gebrochene Relaxation) die aktuell beste Lösung nicht übertreffen kann. Für viele praktische Instanzen ist dies deutlich schneller als DP, wenn W riesig, aber n klein ist. Es ist die Grundlage kommerzieller Solver für ganzzahlige Programmierung wie Gurobi und CPLEX.

Ja. Ein Fully Polynomial-Time Approximation Scheme (FPTAS) erzeugt eine Lösung innerhalb des Faktors (1 − ε) des Optimums in O(n²/ε) Zeit, indem Gegenstandswerte skaliert und gerundet werden. Dies macht die DP-Tabelle für große W klein genug, während nahezu optimale Ergebnisse garantiert werden, und ist ein Meilenstein der Approximationstheorie.

Anwendungen umfassen Frachtbeladung (Maximierung des Umsatzes unter Berücksichtigung von Flugzeuggewichtsgrenzen), Ressourcenzuweisung (Zuweisung von CPU/Speicher an konkurrierende Aufgaben), Portfolioauswahl (Maximierung der Rendite unter einem Budget), Kryptografie (frühe rucksackbasierte Public-Key-Verfahren von Merkle-Hellman, heute gebrochen) und Compiler-Registerzuweisung.

Beim Mehrfach-Rucksackproblem gibt es m Rucksäcke mit jeweils eigener Kapazität, und Gegenstände müssen höchstens einem Rucksack zugewiesen werden. Dies verallgemeinert das Bin-Packing und ist strikt schwieriger; optimale Lösungen erfordern ganzzahlige lineare Programmierung oder Heuristiken wie First-Fit-Decreasing. Es tritt in der Logistik, beim Cloud-VM-Bin-Packing und bei Zuschnittproblemen auf.

Bei der unbeschränkten Variante kann jeder Gegenstand beliebig oft gewählt werden (unbegrenzter Vorrat). Die Rekursion ändert sich zu dp[w] = Maximum über alle i, bei denen wᵢ ≤ w ist, von (dp[w − wᵢ] + vᵢ), unter Verwendung eines einzigen 1D-Arrays, das vorwärts von w = 1 bis W durchlaufen wird. Dies modelliert Szenarien wie Münzwechsel oder das Zerschneiden eines Stabes in Stücke zur Gewinnmaximierung.