Knapsack-Problem¶
Problemstellung¶
Input: Stück-Werte $v_1, v_2, \dots v_n$ und Stück-Größen $s_1, s_2, \dots s_n$ und eine Rucksack-Kapazität $C$ (alles positive Ganzzahlen).
Output: Eine Untermenge $S \subseteq \{1,2,\dots, n\}$ von Stücken mit der maximal möglichen Summe der Werte $\sum_{i\in S} v_i $ mit der Bedingung, dass die Summe der Größen $\sum_{i\in S} s_i $ nicht größer als die Kapazität $C$ ist.
Allgemein einsetzbar für Kosten/Aufwand-Nutzen Optimierung.
- Aufwand/Kosten $\leftrightarrow$ Stück-Größen
- Nutzen $\leftrightarrow$ Stück-Werte
Beispiel¶
| Stück | Wert | Größe | |
|---|---|---|---|
| 1 | 3 | 4 | |
| 2 | 2 | 3 | |
| 3 | 4 | 2 | |
| 4 | 4 | 3 |
Wie groß ist der Gesamtwert der optimalen Lösung für $C=6$?
Optimale Unterstruktur und Rekurrenz¶
Tautologie: $S$ beinhaltet letztes Stück $n$ oder nicht.
Zwei Fälle:
- $n \notin S$: Die optimale Lösung für $n$-Stücke hat den selben Gesamtwert, wie die optimale Lösung für $n-1$ Stücke mit Kapazität $C$.
- $n \in S$: Die optimale Lösung für $n$-Stücke hat den selben Gesamtwert, wie die optimale Lösung für $n-1$ Stücke mit Kapazität $C - s_n$ plus des Wertes $v_n$.
Daraus folgt folgende Rekurrenz für alle $1 \leq i\leq n$ und unter Berücksichtigung, dass ein hinzugefügtes Stück nicht größer als die Kapazität $C$, bzw. die "Restkapazität" $c$ sein darf:
$$ V_{i,c} = \begin{cases} V_{i-1,c} & \text{if } s_i > c\\ \max \left\{V_{i-1,c}, V_{i-1,c-s_i} + v_i \right\} & \text{if } s_i \leq c \end{cases} $$
mit
- $c\in \{0,1,2,\dots,C\}$
- $V_{0,c} = 0$
Erinnerung: $c, s_i$ sind Ganzzahlen.
Dies führt zu folgendem iterativen Algorithmus mit einem 2-d Array A (statt der Rekurrenz):
Knapsack¶
Input: item values $v_1, \dots, v_n$, item sizes $s_1, \dots, s_n$, and a knapsack capacity $C$ (all positive integers)
Output: the maximum total value of a subset $S \subseteq \{1,2,\dots, n\}$ with $\sum_{i\in S} s_i \leq C$
//subproblem solutions (indexed from 0)
$A:= (n+1) \times (C+1)$ two-dimensional array
//base case (i=0)
for $c := 1$ to $C$ do
$A[0][c] := 0$
//systematically solve all subproblems
for $i := 1$ to $n$ do
for $c := 0$ to $C$ do
if $s_i > c$ then
$A[i][c] := A[i-1][c]$
else
$A[i][c] := \max\left\{ A[i-1][c], A[i-1][c-s_i]+v_i \right\}$
return $A[n][C]$
Knapsack Reconstruction¶
Input: the array $A$ computed by the
Knapsackalgorithm with item values $v_1, \dots, v_n$ and item sizes $s_1, \dots, s_n$ and knapsack capacity $C$
Output: an optimal knapsack solution
$S:= \emptyset$
// items in an optimal solutions
$c := C$// remaining capacity
//base case (i=0)
for $ i := n$ downto $1$ do
if $s_i \leq c$ and $A[i-1][c-s_i]+v_i\geq A[i-1][c]$ then
$S := S \cup \{ i \}$\\ case 2 wins, include i
$c := c -s_i$\\ reserve space for it
\\ else skip i, capacity stays the same
return $S$
Theorem 16.6¶
Der
Knapsack-Algorithmus gibt die optimale Lösung für das Knapsack-Problem (in Kombination mit dem Rekonstruktionsalgorithmus) zurück.Laufzeit: $O(nC)$
Literatur¶
- T. Roughgarden, Algorithms Illuminated, Part 3: Greedy Algorithms and Dynamic Programming