Rucksackproblem
aus Freepedia, der freien Wissensdatenbank
Das Rucksackproblem ist ein berühmtes Problem der Informatik und des Operations Research.
Es beschreibt folgende Situation: Es sind verschiedene Gegenstände mit je einem bestimmten Wert und einem bestimmten Volumen vorhanden. Des Weiteren gibt es einen Rucksack mit begrenzter Kapazität (obere Schranke). Die Frage ist, ob der Rucksack derart mit den Gegenständen gefüllt werden kann, dass ihr Gesamtwert eine bestimmte untere Schranke überschreitet.
In der Literatur wird zur Veranschaulichung auch gerne der Dieb herangezogen, der nur einen kleinen Teil der Beute im Rucksack abtransportieren kann und nun versucht, das Maximum herauszuschlagen.
Ein Spezialfall des Rucksackproblems ist PARTITION. Da bereits PARTITION NP-vollständig ist (Reduktion von 3-SAT), ist es auch das Rucksackproblem.
Inhaltsverzeichnis |
Formulierung als Entscheidungsproblem
Gegeben sind eine endliche Menge von Gegenständen <math>U</math>. Mithilfe der Größenfunktion <math>s</math> und der Wertfunktion <math>v</math> wird diesen Gegenständen ein Volumen und ein Wert zugeordnet:
- <math>s:U\rightarrow\mathbb{Z}^+</math>
- <math>v:U\rightarrow\mathbb{Z}^+</math>
Des weiteren gibt es zwei Zahlen <math>B,K \in\mathbb{Z}^+</math>.
Die Frage ist nun, ob es eine Teilmenge <math>U'\subseteq U</math> gibt, so daß
- <math>\sum_{u\in U'} s(u) \le B</math> und <math>\sum_{u\in U'} v(u)\ge K</math>
gilt.
PARTITION ist ein Spezialfall, der auftritt, wenn die Parameter folgendermaßen gewählt werden:
- <math>\forall u\in U:s(u):=v(u)</math> und
- <math>B=K=\frac{1}{2}\sum_{u\in U}s(u)</math>
Anwendungen
Das eingangs beschriebene Rucksackproblem erscheint zunächst als etwas künstliches Problem. Aber viele reale Fragestellungen lassen sich auf dieses Problem bzw. den Lösungsansatz zurückführen.
Oft steht eine begrenzte Kapazität zur Verfügung, welche nicht die gesamte Nachfrage befriedigen kann. Man denke z. B. an einen Lkw, der viele verschiedene Güter – mit einem bestimmten Gewinn – transportieren soll, aber wegen der begrenzten Lademenge nicht alle Güter aufnehmen kann. Der Besitzer des Lkws wird nun so die Ladung wählen, dass der Gewinn maximal ausfällt.
Beispiel
Gegeben sei ein Rucksack mit der Kapazität 12. Außerdem die Objekte A, B und C:
- A: Gewicht=2, Profit=7
- B: Gewicht=5, Profit=15
- C: Gewicht=7, Profit=25
Der Rucksack ist mit dem maximal möglichen Profit zu füllen.
| Kapazität | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| max. Profit | 0 | 7 | 7 | 14 | 15 | 21 | 25 | 28 | 32 | 35 | 39 | 42 |
Anmerkungen
Falls alle Gegenstände ganzzahlige Volumina besitzen, gibt es „schnelle" Algorithmen“, die die optimale Rucksackbelegung in einer Zeit finden, die linear vom Produkt (Rucksackgröße × Anzahl unterschiedlicher Gegenstände) abhängt. Vgl. z. B. Robert Sedgewick: „Algorithms in C“.
Auf Basis von SUBSET-SUM, einem weiteren Spezialfall des Rucksackproblems, wurde das Public-Key-Kryptoverfahren Merkle-Hellman-Kryptosystem entwickelt, das sich allerdings als nicht sicher herausstellte.
