vorige

Rucksack - Problem (knapsack problem)


Zunächst die allgemeine Formulierung des Problems:

Bedingungen: Gegeben sind n Gegenstände und ein Rucksack.
Gewicht:
Jeder Gegenstand hat ein spezielles Gewicht.
Gewinn:
Der Transport jedes Gegenstandes bringt einen speziellen Gewinn.
Ziel:
Gesucht ist eine Kombination der Gegenstände, bei der
  • die Summe ihrer Gewichte die Kapazität des Rucksacks nicht übersteigt
  • und
  • der durch den Transport zu erzielende Gewinn maximal wird.

Das hier beschriebene Problem wird in vielen verschiedenen Ausprägungen untersucht. Die o.a. Formulierung ist die allgemeinste.

Natürlich geht es in der Regel dabei nicht wirklich um einen Rucksack. Er dient begrifflich -wenn auch immer- der Anschaulichkeit. An solche Beschreibungen gewöhnt man sich schnell und sie hat auch dann noch Bestand, wenn der Aspekt der Anschaulichkeit längst verloren gegangen ist. Es gibt zu diesem Problem viele angemessene Anwendungen, die naheliegen. Eine findet sich in LOG IN 2/2000, Rüdeger Baumann, bei der es um eine Anwendung bei der Verschlüsselung geht. Bomze nennt mehrere, z.B. "optimaler Entwurf von technischen Systemen mit redundanten Komponenten" und -was für uns zunächst von größerer Bedeutung ist, die "Darstellung von ganzen Zahlen aus einem Satz von Basiszahlen".

Wir werden uns im Programmbeispiel mit dieser vereinfachten Variante beschäftigen, bei der die Gewinnwerte alle gleich den Gewichten sind. Dann reduziert sich das Problem in der allgemeineren Variante auf die Frage, wie man möglichst viele der Gewichte in den Rucksack bekommt. Wir haben das Problem im Programmbeispiel sogar noch etwas mehr vereinfacht, indem wir fordern, dass das vorgegebene Gesamtgewicht auch wirklich erreicht wird.

So wird aus dem Optimierungsproblem ein reines Satisfizierungsproblem.

Das vereinfachte Problem lautet also:

Vorgabe:
Gegeben seien n positive ganze Zahlen und eine Zielzahl
Ziel:
Gibt es eine Teilmenge von ihnen, deren Summe gleich der Zielzahl ist ?