Lektion 5.3

Das 0/1-Rucksackproblem

20 min Lesezeit
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.

Definition

Das 0/1-Rucksackproblem

Es gibt nn Gegenstände. Gegenstand ii hat ein positives ganzzahliges Gewicht wiw_i und einen nichtnegativen Wert viv_i. Der Rucksack hat eine nichtnegative ganzzahlige Kapazität WW, 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 WW.

Wir müssen die Kapazität nicht genau ausschöpfen. Die leere Auswahl ist erlaubt und hat Gewicht 0 und Wert 0.

Definition

Ein Zustand mit zwei Angaben

Wir schreiben D(i,c)D(i,c) für den größten erreichbaren Wert, wenn wir nur die ersten ii Gegenstände verwenden dürfen und höchstens die Kapazität cc haben. Der Zustand besteht also aus dem Paar (i,c)(i,c).

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 D(0,c)=0D(0,c)=0. Bei Kapazität null gilt wegen der positiven Gewichte D(i,0)=0D(i,0)=0. Die gesuchte Antwort steht am Ende in D(n,W)D(n,W).

Satz

Mitnehmen oder weglassen

Wenn wi>cw_i>c, passt Gegenstand ii nicht in den Rucksack. Dann bleibt nur D(i,c)=D(i−1,c)D(i,c)=D(i-1,c).

Wenn er passt, vergleichen wir zwei Fälle. Ohne ihn erhalten wir D(i−1,c)D(i-1,c). Mit ihm erhalten wir seinen Wert viv_i und dürfen die verbleibende Kapazität c−wic-w_i optimal mit den ersten i−1i-1 Gegenständen belegen.

D(i,c)=max⁡(D(i−1,c),  vi+D(i−1,c−wi))fu¨r wi≤cD(i,c)=\max\bigl(D(i-1,c),\;v_i+D(i-1,c-w_i)\bigr)\quad\text{für }w_i\le c
Beispiel

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ändec=0c=0c=1c=1c=2c=2c=3c=3c=4c=4c=5c=5
Keine000000
A: Gewicht 2, Wert 3003333
A, B: B wiegt 3, Wert 4003447
A, B, C: C wiegt 4, Wert 5003457

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 4+3=74+3=7.

In der letzten Zeile bei Kapazität 5 bringt C nur 5+D(2,1)=5+0=55+D(2,1)=5+0=5. 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.

Beispiel

Vom optimalen Wert zur Auswahl

Wir starten rechts unten bei D(3,5)=7D(3,5)=7. Der Wert steht auch direkt darüber: D(2,5)=7D(2,5)=7. Wir dürfen C also weglassen und gehen zu dieser Zelle.

Dort unterscheidet sich der Wert von D(1,5)=3D(1,5)=3. 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 D(1,2)=3D(1,2)=3.

Dieser Wert ist größer als D(0,2)=0D(0,2)=0. 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.

Häufige Fehler

Eine falsche Tabellenzeile erlaubt denselben Gegenstand mehrfach

Der Ausdruck vi+D(i,c−wi)v_i+D(i,c-w_i) greift auf dieselbe Gegenstandszeile zurück. Dort darf Gegenstand ii aber bereits verwendet worden sein. Durch erneutes Addieren seines Werts könnten wir ihn mehrfach einpacken.

Richtig ist

Beim 0/1-Rucksackproblem muss der Restwert aus Zeile i−1i-1 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.

  • D(i,c)D(i,c) beschreibt den besten Wert mit den ersten ii Gegenständen und Kapazität höchstens cc.

  • 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

Aufgabe 1Numerisch

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?

Aufgabe 2Multiple Choice

Welche Restfrage passt zum Mitnehmen von Gegenstand ii?

Aufgabe 3Numerisch

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?

Aufgabe 4Freitext

Warum beweist die Laufzeit O(nW)O(nW) keine polynomielle Laufzeit in der Länge der binär geschriebenen Eingabe?