Definition:
Das Problem Knapsack (Rucksackproblem) ist die Suche nach einer optimalen Rucksackpackung, so dass
die eingepackten Objekte ein Gesamtgewicht nicht überschreiten und ihr Wert maximal ist.
Lösung: (Dynamische Programmierung)
Seien die Objekte aufsteigend nummeriert und sei das minimal mögliche Gewicht des Rucksacks,
das mit einer Auswahl der ersten Objekte den Profit erreicht.
Entweder das -te Objekt gehört zur Teilmenge mit minimalem Gewicht oder nicht:
Komplexität:
Das Problem Knapsack hat Laufzeit
. Gemäß log. Kostenmaß ist es jedoch -schwer.
Definition:
Ein Algorithmus heißt pseudo-polynomial, falls seine Laufzeit in der Länge der Eingabe und der
größten in der Eingabe vorkommenden Zahl festgelegt ist.
Bemerkung:
Pseudo-polynomiale Algorithmen verhalten sich in der Praxis etwa so gut wie polynomiale Algorithmen.
Knapsack ist ein pseudo-polynomialer Algorithmus.
Approximationsalgorithmus:
Skalierung der Profite mit Faktor
liefert
. Dann gilt:
.
Laufzeit der dynamischen Programmierung ist somit
.
Für die erhaltene Lösung gilt
.
Korollar: Knapsack