Das 0/1-Rucksackproblem
Lesen anpassen
Nach dieser Lektion kannst du
Den Zustand einer Optimierungsaufgabe aus den verbleibenden Entscheidungen ableiten.
Den Übergang zwischen Mitnehmen und Weglassen eines Gegenstands begründen.
Aus einer Wertetabelle eine optimale Auswahl zurückverfolgen.
Vorausgesetzt: Memoisierung und Tabellen: zwei Wege zur gleichen Lösung
Ein Rucksack kann höchstens fünf Gewichtseinheiten tragen. Zur Auswahl stehen drei unteilbare Gegenstände. Gegenstand A wiegt 2 und hat den Wert 3, B wiegt 3 und hat den Wert 4, C wiegt 4 und hat den Wert 5. Jeder Gegenstand ist genau einmal vorhanden. Welche Auswahl bringt den größten Gesamtwert?
Der wertvollste einzelne Gegenstand ist C. Er füllt den Rucksack fast vollständig und lässt keinen Platz für einen weiteren Gegenstand. A und B passen dagegen gemeinsam hinein und haben zusammen den Wert 7. Die naheliegende Entscheidung für den größten Einzelwert wäre hier also falsch.
Wir suchen deshalb systematisch das Beste unter allen zulässigen Auswahlen. Statt alle Auswahlen immer wieder neu zu untersuchen, speichern wir, was mit einer kleineren Auswahl an Gegenständen und einer kleineren Kapazität bereits erreichbar ist.
Das 0/1-Rucksackproblem
Es gibt Gegenstände. Gegenstand hat ein positives ganzzahliges Gewicht und einen nichtnegativen Wert . Der Rucksack hat eine nichtnegative ganzzahlige Kapazität , also eine Obergrenze für das Gesamtgewicht.
Für jeden Gegenstand entscheiden wir zwischen genau zwei Möglichkeiten: nicht mitnehmen oder einmal mitnehmen. Daher heißt das Modell 0/1-Rucksackproblem. Teilen und mehrfaches Verwenden sind ausgeschlossen. Ziel ist der größte Gesamtwert bei einem Gesamtgewicht von höchstens .
Wir müssen die Kapazität nicht genau ausschöpfen. Die leere Auswahl ist erlaubt und hat Gewicht 0 und Wert 0.
Ein Zustand mit zwei Angaben
Wir schreiben für den größten erreichbaren Wert, wenn wir nur die ersten Gegenstände verwenden dürfen und höchstens die Kapazität haben. Der Zustand besteht also aus dem Paar .
Die Zahl der betrachteten Gegenstände ist nötig, damit wir jeden Gegenstand höchstens einmal verwenden. Die Kapazität ist nötig, weil bei weniger Platz andere Auswahlen möglich sind.
Ohne Gegenstände gilt . Bei Kapazität null gilt wegen der positiven Gewichte . Die gesuchte Antwort steht am Ende in .
Mitnehmen oder weglassen
Wenn , passt Gegenstand nicht in den Rucksack. Dann bleibt nur .
Wenn er passt, vergleichen wir zwei Fälle. Ohne ihn erhalten wir . Mit ihm erhalten wir seinen Wert und dürfen die verbleibende Kapazität optimal mit den ersten Gegenständen belegen.
Jede zulässige Auswahl enthält Gegenstand entweder nicht oder genau einmal. Im ersten Fall kann ihr Wert nicht größer als sein. Im zweiten Fall lässt das Entfernen von eine zulässige Auswahl der ersten Gegenstände mit Kapazität zurück.
Wäre diese verbleibende Auswahl nicht optimal, könnten wir sie durch eine bessere ersetzen und zusammen mit einen größeren Gesamtwert erreichen. Beide in der Formel betrachteten Werte sind andererseits durch zulässige Auswahlen erreichbar. Ihr Maximum ist deshalb genau der optimale Wert.
Die Tabelle für drei Gegenstände
Die Tabelle für drei Gegenstände
Wir bearbeiten A, dann B, dann C. Die Spalten stehen für die Kapazität, die Zeilen für die Gegenstände, die bereits zur Verfügung stehen.
| Erlaubte Gegenstände | ||||||
|---|---|---|---|---|---|---|
| Keine | 0 | 0 | 0 | 0 | 0 | 0 |
| A: Gewicht 2, Wert 3 | 0 | 0 | 3 | 3 | 3 | 3 |
| A, B: B wiegt 3, Wert 4 | 0 | 0 | 3 | 4 | 4 | 7 |
| A, B, C: C wiegt 4, Wert 5 | 0 | 0 | 3 | 4 | 5 | 7 |
Betrachten wir die zweite Gegenstandszeile bei Kapazität 5. Ohne B ist der beste Wert 3. Mit B bleibt Kapazität 2; aus der vorherigen Zeile lesen wir dort den Wert 3 für A. Zusammen ergeben sich .
In der letzten Zeile bei Kapazität 5 bringt C nur . Weglassen liefert bereits 7. Deshalb bleibt der Eintrag 7.
Ein Tabelleneintrag ist ein Wert, keine Liste von Gegenständen. Die Auswahl rekonstruieren wir gesondert. Die neue Zeile verwendet ausschließlich Werte aus der vorherigen Zeile; dadurch kann ihr neuer Gegenstand nicht mehrfach vorkommen.
Vom optimalen Wert zur Auswahl
Vom optimalen Wert zur Auswahl
Wir starten rechts unten bei . Der Wert steht auch direkt darüber: . Wir dürfen C also weglassen und gehen zu dieser Zelle.
Dort unterscheidet sich der Wert von . B muss in einer Auswahl enthalten sein, die den Wert 7 erreicht. Wir notieren B, ziehen sein Gewicht 3 von der Kapazität ab und gehen zu .
Dieser Wert ist größer als . Wir nehmen deshalb auch A und reduzieren die Kapazität um 2. Die Rückverfolgung endet bei Kapazität 0. Die Auswahl A und B hat Gewicht 5 und Wert 7.
Sind der Eintrag und sein Vorgänger gleich, kann es mehrere optimale Auswahlen geben. Weglassen ist dann eine zulässige Entscheidung, aber nicht zwingend die einzige. Ein Verfahren muss nicht jede optimale Auswahl ausgeben, um eine korrekte zu liefern.
Eine falsche Tabellenzeile erlaubt denselben Gegenstand mehrfach
Eine falsche Tabellenzeile erlaubt denselben Gegenstand mehrfach
Der Ausdruck greift auf dieselbe Gegenstandszeile zurück. Dort darf Gegenstand aber bereits verwendet worden sein. Durch erneutes Addieren seines Werts könnten wir ihn mehrfach einpacken.
Beim 0/1-Rucksackproblem muss der Restwert aus Zeile kommen. Wenn nur ein eindimensionales Feld gespeichert wird, werden Kapazitäten für jeden Gegenstand absteigend durchlaufen. Dann sind die kleineren Kapazitäten beim Lesen noch Werte des vorherigen Durchlaufs.
Zusammenfassung
0/1 bedeutet, dass jeder unteilbare Gegenstand höchstens einmal vorkommt.
beschreibt den besten Wert mit den ersten Gegenständen und Kapazität höchstens .
Der Übergang vergleicht Weglassen mit Mitnehmen und verwendet dabei die vorherige Zeile.
Eine Rückverfolgung durch die Tabelle liefert zusätzlich zum Wert eine optimale Auswahl.
Die Laufzeit hängt vom Zahlenwert der Kapazität ab und ist pseudopolynomiell.
Übungen
Im Beispiel sind A (Gewicht 2, Wert 3), B (Gewicht 3, Wert 4) und C (Gewicht 4, Wert 5) verfügbar. Welcher größte Wert passt bei Kapazität 4?
Welche Restfrage passt zum Mitnehmen von Gegenstand ?
Ein einziger Gegenstand hat Gewicht 2 und Wert 3. Die Kapazität beträgt 4. Welcher größte Wert ist im 0/1-Modell möglich?
Warum beweist die Laufzeit keine polynomielle Laufzeit in der Länge der binär geschriebenen Eingabe?