Bei der Knapsack-Optimierung, die auch als Rucksackproblem bekannt ist, handelt es sich um ein bekanntes logisches Problem der kombinatorischen Optimierung, bei dem eine begrenzte Menge an Ressourcen auf eine Menge von Elementen verteilt werden soll. Jedes Element hat einen bestimmten Wert und eine gewisse Größe, und das Ziel ist es, die Elemente auszuwählen, die den größtmöglichen Gesamtwert haben, ohne dabei die Kapazität des Rucksacks zu überschreiten.
Das Problem erhielt seinen Namen von der Analogie mit einem Rucksacks, der mit Gegenständen gefüllt werden soll, wobei dieser eine begrenzte Kapazität hat, und die Aufgabe besteht darin, die wertvollsten Gegenstände auszuwählen, die hineinpassen. Die Knapsack-Optimierungals gilt stilisierte Darstellung der Schwierigkeit von Aufgaben des täglichen Lebens. Es sind z. B. verschiedene Gegenstände mit einem bestimmten Gewicht und einem Nutzwert gegeben, wobei aus diesen Gegenständen nun eine Auswahl getroffen werdensoll, die in einen Rucksack mit einer vorgegebenen Gewichtsschranke mitgenommen werden können. Viele reale Situationen lassen sich mit Hilfe der Lösung dieses Problems mathematisch klären, denn oft steht eine begrenzte Kapazität zur Verfügung, die nicht die gesamte Nachfrage befriedigen kann. Man denke etwa 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 die Ladung dahrt so wählen, dass der Gewinn maximal ausfällt. In der Literatur wird übrigens zur Veranschaulichung auch gerne der Dieb herangezogen, der nur einen kleinen Teil seiner Beute im Rucksack abtransportieren kann und nun versucht, das Maximum an Nutzwert herauszuschlagen.
Dabei gibt es verschiedene Varianten des Knapsack-Problems, wie zum Beispiel das 0/1-Knapsack-Problem, bei dem jedes Element entweder vollständig aufgenommen oder ausgelassen werden muss, oder das unbeschränkte Knapsack-Problem, bei dem Elemente in beliebiger Menge aufgenommen werden können. Die Knapsack-Optimierung findet Anwendungen in verschiedenen Bereichen wie Logistik, Finanzplanung, Ressourcenmanagement und Informatik, wobei es keinen bekannten effizienten Algorithmus gibt, der das Problem in einer bestimmten Zeit löst. Es werden jedoch verschiedene Algorithmen und Heuristiken verwendet, um eine gute Lösung für das Knapsack-Problem zu finden, einschließlich dynamischer Programmierung, Greedy-Algorithmen und genetischer Algorithmen.
Literatur
Kellerer, H., Pferschy, U. & Pisinger, D. (2004). Knapsack Problems. Berlin: Springer.