Rucksackproblem
Einfache Sprache
Das Rucksackproblem ist ein Entscheidungsproblem wo man aus $n$ Gegenständen auswählen soll so, dass das der Rucksack einen mindest Wert hat und ein maximal Gewicht nicht überschreitet.
Problemstellung:
Gegeben: $n$ Gegenstände mit Größen $c_1,\ldots,c_n$ und Gewinnen $p_1,\ldots,p_n$ und Rucksackkapazität $K$ und Profitwert $P$. Entscheide: Gibt es eine Teilmenge $S\subseteq\{1,\ldots,n\}$ der $n$ Gegenstände mit Gesamtgröße $\sum_{j\in S}c_j\leq K$ und Gesamtprofit $\sum_{j\in S}p_j\geq P$.
Satz: Rucksackproblem
Das Rucksackproblem ist NP-vollständig.
Exakte Lösung
Mithilfe von Dynamische Programmierung
Idee
Es wird immer eine neuer Gegenstand hinzugefügt und geschaut ob sich die optimale Lösung für alle Profit-Summen ändert. Das heißt konkret: Für ein Gesamtprofit von $p_g$ aus $1$ bis $n$ Gegenständen wird das Gewichtsminimum aus (1) der optimalen Lösung für $p_g$ aus $1$ bis $n-1$ Gegenständen oder (2) der optimalen Lösung für $p_g-p_n$ plus das Gewicht des neuen Gegenstands $w_n$.
\begin{algorithm}
\caption{Knapsack}
\begin{algorithmic}
\Input Liste an Gegenständen $L = [(w_0,p_0),\ldots,(w_{n-1},p_{n-1})]$ und Rucksackkapazität $B$
\Procedure{KNAPSACk-DP}{$L,B$}
\State $n = \textrm{length}(L)$
\State $\textrm{maxprofit} = 0$
\For{$i = 0$ \textbf{ to } $n-1$}
\State $\textrm{maxprofit} = \textrm{maxprofit} + p_j$
\EndFor
\State Erzeuge ein 2D-Feld $A$ mit $[n,\textrm{maxprofit+1}]$ Elementen
\State $A[0,0] = 0$
\For{$t = 1$ \textbf{ to }$\textrm{maxprofit}$}
\If{$p_0 \not=t$}
\State $A[0,t] = B+1$
\Else
\State $A[0,t] = w_0$
\EndIf
\EndFor
\For{$i = 1$ \textbf{ to } $n-1$}
\For{$t = 0$ \textbf{ to } $\textrm{maxprofit}$}
\If{$t<p_i$}
\State $A[i,t] = A[i-1,t]$
\Else
\State $A[i,t] = \min(A[i-1,t], A[i-1,t-p_i]+w_i)$
\EndIf
\EndFor
\EndFor
\State $j = 0$
\For{$t = 0$ \textbf{ to }$\textrm{maxprofit}$}
\If{$A[n-1,t]\leq B$}
\State $j = t$
\EndIf
\EndFor
\Return j
\EndProcedure
\end{algorithmic}
\end{algorithm}
Der Algorithmus $\textrm{KNAPSACK-DP}$ hat eine Laufzeit von $\mathcal O(\textrm{maxprofit}\cdot n)$, wobei $\textrm{maxprofit}=\sum_{i=0}^{n-1}p_i$.
Worst-case -> Laufzeit ist exponentiell
Approximative Lösung
Greedy-Algorithmus
Idee Greedy-Rucksack
Es werden nur die Gegenstände in den Rucksack getan die das best Profit-Gewicht-Verhältnis haben. Dazu geht man die Gegenstände im Absteigenden Profit-Gewicht-Verhältnis durch und schaut ob sie noch in den Rucksack passen.
\begin{algorithm}
\caption{greedy Knapsack}
\begin{algorithmic}
\Input Liste an Gegenständen $L = [(w_0,p_0),\ldots,(w_{n-1},p_{n-1})]$ und Rucksackkapazität $B$
\Procedure{KNAPSACk-GA}{$L,B$}
\State Sortiere $L$ so, dass $p_0/w_o \leq p_1/w_1\leq\ldots\leq p_{n-1}/w_{n-1}$
\State Setze $S=\emptyset$
\For{$i = 0$ \textbf{ to } $n-1$}
\If{$\sum_{j\in S}w_j+w_i\leq B$}
\State $S=S \cup \{i\}$
\EndIf
\EndFor
\Return S
\EndProcedure
\end{algorithmic}
\end{algorithm}
Die Laufzeit von $\textrm{KNAPSACK-GA}$ ist $\mathcal O(n\log n)$. Die multiplikative Güte ist größer gleich $B-1$, d.h. $\textrm{OPT}(I)/\textrm{KNAPSACK-GA}(I)\geq B-1$.
Idee Modifizierter Greedy-Rucksack
Um die Güte besser beschränken zu können, wird beim modifizierten Greedy-Rucksack zusätzlich dir Option betrachtet den Gegenstand mit maximalen Profit (nicht Profit-Gewicht-Verhältnis) als einziges Element im Rucksack.
\begin{algorithm}
\caption{modified greedy Knapsack}
\begin{algorithmic}
\Input Liste an Gegenständen $L = [(w_0,p_0),\ldots,(w_{n-1},p_{n-1})]$ und Rucksackkapazität $B$
\Procedure{KNAPSACk-MGA}{$L,B$}
\State $S_1 = $ \Call{KNAPSACK-GA}{$L,B$}
\State Berechne Lösung $S_2 = \{j\}$ mit $p_j = \max_{i\in\{0,\ldots,n-1\}}p_i$
\State Wähle Lösung $S\in\{S_1,S_2\}$ mit größerem Profit.
\Return S
\EndProcedure
\end{algorithmic}
\end{algorithm}
Die Laufzeit von $\textrm{KNAPSACK-MGA}$ ist auch $\mathcal O(n\log n)$. Die Worst-case Güte ist $2$, d.h. $\textrm{OPT}(I)/\textrm{KNAPSACK-MGA}(I)\leq 2$.