Rucksackproblem

Rucksackproblem Definition

Das Rucksackproblem (international auch als Knapsack-Problem bekannt) ist ein modellhaftes kombinatorisches Optimierungsproblem, das allgemein so aussieht:

Man hat einen Rucksack mit einer maximalen Traglast (in kg) sowie eine Anzahl von Gegenständen mit Gewichten (in kg) und Werten (z.B. in Euro).

Man soll die optimale Kombination von Gegenständen (mit dem höchsten Gesamtwert) finden, die Traglast darf dabei nicht überschritten werden.

Wir stellen uns für ein Beispiel einen Einbrecher im Juweliergeschäft vor:

Beispiel

Die maximale Traglast des Rucksacks sei 10 kg. Der Einbrecher hat 5 Gegenstände im Visier:

  • 5 kg-Goldbarren, Wert 100.000 €
  • 7-kg-Silberbarren, Wert 60.000 €
  • 3 kg-Platinbarren, Wert 80.000 €
  • Geldkassette, wiegt 4 kg, Inhalt: 90.000 €
  • Schmuckschatulle, wiegt 2 kg, Wert 60.000 €

Was soll der Einbrecher einpacken, damit seine Beute möglichst hoch, die Traglast des Rucksacks aber nicht überschritten wird? (sonst reißt dieser bei der Flucht und alles ist verloren.)

In diesem einfachen Beispiel "sieht" man die Lösung einigermaßen schnell (Computer / Programme können aber nicht sehen, sie brauchen einen Algorithmus, der dann auch bei mehr Gegenständen funktioniert).

Es gibt mehrere Möglichkeiten, das Rucksackproblem zu lösen:

  • vollständige Aufzählung aller möglichen Kombinationen (das können Millionen sein);
  • Branch-and-Bound-Verfahren;
  • dynamische Programmierung.

Das Rucksackproblem ist wie gesagt ein Modell; es geht nicht wirklich darum, Rucksäcke zu packen, sondern um andere, v.a. ökonomische Fragen.