Das Rucksackproblem
Eine Wanderin mit Gewichtsgrenze, ein Dieb mit einem Sack, eine Firma mit einem Budget und einer Liste von Projekten: Alle stehen vor derselben Frage. Was soll hinein, um den größten Wert zu erreichen, ohne die Grenze zu überschreiten? Das ist das Rucksackproblem, und die dynamische Programmierung löst es exakt, wenn die Gewichte ganze Zahlen von mäßiger Größe sind.
Das Problem
Es gibt n Gegenstände, jeder mit einem Gewicht und einem Wert, und einen Rucksack, der höchstens das Gewicht W fasst. Wählen Sie eine Menge von Gegenständen, deren Gesamtgewicht höchstens W ist und deren Gesamtwert so groß wie möglich ist. Jeder Gegenstand kommt ganz hinein oder bleibt draußen, deshalb heißt es 0/1-Rucksackproblem. Bei n Gegenständen gibt es 2ⁿ mögliche Mengen, sodass es bald unmöglich wird, alle auszuprobieren.
Die Tabelle
Sei best[i][w] der größte Wert, der mit nur den ersten i Gegenständen in das Gewicht w passt. Dann ist best[0][w] = 0, und für jede weitere Zeile gibt es zwei Möglichkeiten: Gegenstand i weglassen, was best[i − 1][w] ergibt, oder, wenn sein Gewicht wᵢ passt, ihn einpacken, was seinen Wert plus best[i − 1][w − wᵢ] ergibt. Der größere Wert ist best[i][w]. Wenn man die Tabelle Zeile für Zeile füllt, sind beide Zellen, die man braucht, immer schon fertig.
Ein Beispiel
Nehmen Sie eine Kapazität von 7 und vier Gegenstände mit den Gewichten 1, 3, 4 und 5 und den Werten 1, 4, 5 und 7. Mit nur dem ersten Gegenstand hat jede Kapazität ab 1 den Wert 1. Mit dem zweiten kann Kapazität 4 beide aufnehmen, für 5. Mit dem dritten kann Kapazität 7 die Gegenstände 2 und 3 aufnehmen, für 9. Der vierte Gegenstand, Gewicht 5 und Wert 7, könnte bei Kapazität 6 oder 7 zusammen mit Gegenstand 1 auf 8 kommen, aber 9 ist besser, also ist die Zelle unten rechts 9: Packen Sie die Gegenstände mit Gewicht 3 und 4 ein.
Wie schwer ist es?
Die Tabelle braucht etwa n·W Schritte. Das sieht schnell aus, aber W ist eine Zahl, und eine Zahl mit d Stellen kann so groß sein wie 10 hoch d, sodass der Aufwand exponentiell mit der Länge der Eingabe wächst. Das Rucksackproblem ist NP-schwer; es war eines der 21 NP-vollständigen Probleme von Richard Karp aus dem Jahr 1972. In der Praxis bewältigen die Tabelle, Branch and Bound und gute Approximationsschemata auch große reale Fälle gut.
Geschichte und Anwendungen
Der Name geht auf den Mathematiker Tobias Dantzig im frühen 20. Jahrhundert zurück, und sein Sohn George Dantzig stellte 1957 ein klassisches Greedy-Verfahren dafür vor. Rucksackprobleme tauchen bei der Budgetplanung und der Portfolioauswahl auf, beim Zuschneiden von Rohmaterial mit möglichst wenig Verschnitt, beim Beladen mit Fracht und sogar in der frühen Public-Key-Kryptografie: Das Merkle–Hellman-Kryptosystem von 1978 beruhte auf einem Rucksackproblem und wurde wenige Jahre später gebrochen.
Selbst ausprobieren
Öffnen Sie die App, wechseln Sie zur Ansicht Tabelle und drücken Sie Schritt. Die orange Zelle wird gerade gefüllt, und die blauen Zellen sind die beiden, die sie vergleicht: die Zelle direkt darüber und, in der Zeile darüber, die Zelle, die um das Gewicht des Gegenstands nach links versetzt ist. Nach der letzten Zelle steigt das Ablesen in Orange von der Ecke unten rechts nach oben, und die eingepackten Gegenstände erscheinen unter der Tabelle.
Häufig gestellte Fragen
Was ist der Unterschied zwischen dem 0/1-, dem beschränkten und dem unbeschränkten Rucksackproblem?
In der 0/1-Variante wird jeder Gegenstand höchstens einmal genommen. In der beschränkten Variante gibt es von jedem Gegenstand eine begrenzte Anzahl von Exemplaren, in der unbeschränkten beliebig viele. Die Tabelle ändert sich zwischen ihnen nur wenig.
Ist das Greedy-Verfahren beim Rucksackproblem jemals richtig?
Beim fraktionalen Rucksackproblem, bei dem sich Gegenstände teilen lassen, ist es optimal, zuerst den besten Wert pro Gewicht zu nehmen. Bei ganzen Gegenständen kann es weit danebenliegen, allerdings ist das Bessere aus Greedy-Lösung und dem einzelnen wertvollsten Gegenstand immer mindestens halb so viel wert wie der beste Wert.
Wie viel Speicher braucht die Tabelle?
(n + 1)·(W + 1) Zellen für die volle Tabelle, und die brauchen Sie, um die Gegenstände abzulesen. Wenn nur der beste Wert gefragt ist, reicht eine Zeile mit W + 1 Zellen, die von rechts nach links gefüllt wird.
Ist das Rucksackproblem dasselbe wie das Teilsummenproblem?
Das Teilsummenproblem (Subset Sum) ist der Spezialfall, bei dem der Wert jedes Gegenstands gleich seinem Gewicht ist und die Frage lautet, ob sich der Rucksack genau füllen lässt. Es ist ebenfalls NP-vollständig und wird mit derselben Art von Tabelle gelöst.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Rucksackproblem ausprobieren