- Wird gefüllt
- Wird gelesen
- Ergebnis
Rucksackproblem
Sie können nur ein bestimmtes Gewicht tragen, und jeder Gegenstand hat ein Gewicht und einen Wert. Welche Gegenstände nehmen Sie mit, um den größten Wert zu tragen? Jede Kombination auszuprobieren verdoppelt den Aufwand mit jedem Gegenstand. Eine Tabelle mit Gegenständen als Zeilen und Kapazitäten als Spalten findet den besten Rucksack Zelle für Zelle. Tippen Sie auf einen Gegenstand, um ihn in den Rucksack zu legen, und tippen Sie erneut darauf (im Rucksack oder im Regal), um ihn wieder herauszunehmen. Der Rucksack füllt sich nach Gewicht, und die Kacheln zeigen die eingepackten Dollar im Vergleich zum bestmöglichen Wert. Drücken Sie Optimal packen, um den besten Rucksack zu sehen. Im Bedienfeld können Sie die Kilogramm und Dollar der Gegenstände ändern, Gegenstände hinzufügen oder entfernen und die Rucksackkapazität festlegen. Die Ansicht Tabelle zeigt, wie dynamische Programmierung den besten Rucksack findet: Drücken Sie Abspielen, um zuzusehen, wie sich die Tabelle füllt, oder Schritt und Zurück, um jeweils einen Schritt zu gehen, und ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Jede Zeile nimmt einen Gegenstand hinzu, jede Spalte ist eine Kapazität in Kilogramm, und jede Zelle enthält den höchsten Dollarbetrag, der hineinpasst. Wenn die Tabelle ausgewählt ist, gehen die Pfeiltasten schrittweise vor und zurück, die Leertaste startet und pausiert die Wiedergabe, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Tippen Sie auf die Kisten, um sie in den Rucksack zu packen, und sehen Sie, wie er sich nach Gewicht in Kilogramm füllt.
- Versuchen Sie, den bestmöglichen Wert in Dollar zu erreichen, oder drücken Sie Optimal packen, um die beste Füllung zu sehen.
- Öffnen Sie die Ansicht Tabelle und drücken Sie Abspielen, um zu sehen, wie jede Zelle zwischen Einpacken und Weglassen eines Gegenstands wählt.
So funktioniert die Tabelle
Jede Zeile nimmt einen Gegenstand hinzu, und jede Spalte ist eine Kapazität von 0 bis zur Kapazität des Rucksacks. Eine Zelle enthält den größten Wert, der mit den Gegenständen bis zu ihrer Zeile in diese Kapazität passt. Ohne den neuen Gegenstand ist das die Zelle darüber. Mit ihm, falls er passt, ist es der Wert des Gegenstands plus der beste Wert für das restliche Gewicht; der steht in der Zeile darüber, um das Gewicht des Gegenstands nach links versetzt. Die Zelle behält den größeren der beiden Werte. Die erste Zeile, ohne Gegenstände, besteht nur aus Nullen.
Die Gegenstände ablesen
Die Zelle unten rechts ist der beste Wert. Um die Gegenstände zu finden, beginnen Sie dort und vergleichen sie mit der Zelle darüber: Ist sie gleich, wurde der letzte Gegenstand nicht gebraucht; ist sie größer, ist der Gegenstand im Rucksack, also ziehen Sie sein Gewicht ab und gehen zu dieser Spalte. Gehen Sie jedes Mal eine Zeile nach oben, bis zur ersten Zeile. Die App zeigt dieses Ablesen in Orange und listet die eingepackten Gegenstände unter der Tabelle auf.
Häufig gestellte Fragen
Was bedeutet 0/1 beim 0/1-Rucksackproblem?
Jeder Gegenstand wird einmal oder gar nicht eingepackt, nie zum Teil und nie zweimal. Könnte man Gegenstände teilen, wie Reiskörner, wäre es optimal, zuerst den besten Wert pro Gewicht einzupacken; das ist das fraktionale Rucksackproblem.
Warum nicht zuerst den besten Wert pro Gewicht einpacken?
Weil ganze Gegenstände Lücken lassen können. Bei einer Kapazität von 7 und Gegenständen mit den Gewichten 1, 3, 4 und 5 und den Werten 1, 4, 5 und 7 hat der Gegenstand mit Gewicht 5 den besten Wert pro Gewicht; daneben ist nur noch Platz für den Gegenstand mit Gewicht 1, zusammen 8. Die Gegenstände mit Gewicht 3 und 4 sind zusammen 9 wert.
Wie schnell ist der Rucksack-Algorithmus?
Die Tabelle hat (Anzahl der Gegenstände + 1) mal (Kapazität + 1) Zellen, und jede wird in einem Schritt gefüllt. Das geht bei kleinen Kapazitäten schnell, aber eine Kapazität kann eine riesige Zahl sein, deshalb ist das Problem im Allgemeinen NP-schwer; die Tabellenmethode nennt man pseudopolynomiell.
Kann derselbe Gegenstand zweimal eingepackt werden?
Hier nicht. Beim unbeschränkten Rucksackproblem darf jeder Gegenstand beliebig oft genommen werden; die Tabelle liest dann die Zelle links in derselben Zeile statt der Zeile darüber, wie in der App zum Wechselgeldproblem.
Wird irgendetwas übertragen?
Nein. Alles wird in Ihrem Browser berechnet, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor