Knapsack

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 $f(i,t)$ das minimal mögliche Gewicht des Rucksacks, das mit einer Auswahl der ersten $i$ Objekte den Profit $t$ erreicht.
Entweder das $i$-te Objekt gehört zur Teilmenge mit minimalem Gewicht oder nicht:
$f(i,t) = min \{ \omega_i + f(i-1,t-p_i), \> f(i-1,t) \}$

Komplexität:
Das Problem Knapsack hat Laufzeit $O(n^2 p_{max})$. Gemäß log. Kostenmaß ist es jedoch $NP$-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 $K_{\epsilon}$ liefert $p_i' = p_i / K_{\epsilon}$. Dann gilt:
$p_{max}' \leq \frac{p_{max}}{\epsilon} = \frac{n}{\epsilon}$.
Laufzeit der dynamischen Programmierung ist somit $O(n^3 / \epsilon)$.
Für die erhaltene Lösung gilt $A(I) \geq (1-\epsilon) OPT(I)$.

Korollar: Knapsack $\in FPTAS$