Algorithmus von Sahni

Einfache Sprache

Um das Rucksackproblem zu lösen wird ein Teil der Lösung im trial and error gefunden und dann mit einem Greedy-Algorithmus kombiniert.

Idee Algorithmus von Sahni

Der Algorithmus von Sahni probiert alle $k$-einelementigen Teilmengen der Gegenstände durch, in dem er sie in den Rucksack vorplatziert, wenn möglich, und mit Hilfe des Greedy Rucksack Algortihmus die Restkapazität auffühlt.

	\begin{algorithm}
	\caption{Algorithmus von Sahni}
	\begin{algorithmic}
	\Input Menge an Gegenständen $S = [(w_0,p_0),\ldots,(w_{n-1},p_{n-1})]$, ein Paramter $k\in\{0,\ldots,n\}$ und Rucksackkapazität $B$
	\Procedure{Sahni}{$S,k,B$}
	\ForAll{$T\in S$ mit $|T|\leq k$}
		\State Lege $T$ in den Rucksack
		\State Wende $\textrm{KNAPSACK-GA}$ auf die übrigen Gegenstände $S\setminus T$ an auf die Restkapazität des Rucksacks
    \EndFor
    \Return Rucksack mit maximalen Gewinn
    \EndProcedure
	\end{algorithmic}
	\end{algorithm}

Der Algorithmus von Sahni hat eine Laufzeit von $\mathcal O(n^{k+1})$ und hat eine Güte von $\leq 1+1/k$.