AuKAuKAuK43

Lösung des 0/1 Rucksackproblems

Beim Rucksackproblem handelt es sich um ein Optimierungsproblem der Kombinatorik. Aus einer bestimmten Menge von Objekten, die jeweils ein Gewicht und einen Wert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht ein vorgegebenes Gewichtslimit nicht überschreitet. Hierbei gilt die Optimalitätsbedingung, denn die optimale Gesamtlösung lässt sich aus optimalen Teilproblemen zusammensetzen. Bezogen auf das Rucksackproblem bedeutet das, Gegenstand i wird in den optimal gefüllten, auch leeren, Rucksack gelegt. D.h. alle zur Auswahl stehenden Gegenstände können solange in den Rucksack gelegt werden, solange sie noch Platz haben.

Für den optimal gefüllten Rucksack gilt die rekursive Definition mit:

$wert(i,g) = \begin{cases} 0, & wenn \ i =0 \\ wert(i-1, g), & wenn \ i > 0 \ und \ g-g_{i} < 0\\ max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i}), & sonst \\ \end{cases}$

Der Fall wert(i,g) = wert(i-1,g) bezieht sich auf einen Gegenstand, der die Restkapazität des Rucksacks überschreiten würde. D.h. wert(i-1,g) ist der Maximalwert aus 1,2,...,i-1 Gegenständen mit Bezug auf die Kapazität des Rucksacks. Der letzte Fall wert(i,g) = max(wert(i-1,g), wert(i-1, g-g_{i})+w_{i}) beschreibt die Maximierung des Wertes in Berücksichtigung des Gewichtes.

Iterativer Algorithmus

Der iterative Lösungsansatz lässt sich, wie bereits erwähnt, nicht mit einer rekursiven Vorschrift umsetzen. Jedoch ist es möglich, die Überlegungen aus dieser Vorschrift zu verwenden und in einen iterativen Lösungsansatz umzuwandeln.

Das soll am folgenden Beispiel demonstriert werden:

Zur Lösung wird die Gegenstandsliste mit der Prozedur gegenstaende (Quelle: [1], S. 102) auf Vektoren als Gewicht/Wert-Paar abgebildet. Auf das jeweilige Gewicht bzw. den jeweiligen Wert kann dann mittels der Prozeduren gewicht und wert zugegriffen werden. Die Prozedur gesamtwert-iterativ füllt dann eine Tabelle mit den jeweils maximalen Gesamtwerten für die aktuell betrachteten Gegenstände (Zeile) und das darauf bezogene Gesamtgewicht (Spalte). Das Problem hierbei ist die Speicherung aller Werte in der Tabelle, was eine sehr hohe Speicherbelastung nach sich zieht. Für den hier dargestellten Fall genügt es jedoch, wie in der rekursiven Vorschrift notiert, die jeweils letzten beiden Zeilen (zeileAlt und zeileNeu) zu speichern. D.h. die i-te Zeile wird aus der i-1-ten Zeile berechnet.

Der Aufruf von (gesamtwert-iterativ 5 10) erzeugt folgende Tabelle:

Aufwandsbetrachtung

An der iterativen Prozedur kann man sehr gut erkennen, dass sich der Aufwand aus der Berechnung der Tabelle mit allen Spalten und Zeilen ergibt.

Nimmt man nun an, dass K eine Konstante ist, ergibt sich ein linearer Aufwand \mathcal O(n). Doch da für alle n Gegenstände gilt, dass g_i \le K ist, lässt sich ein Zusammenhang zwischen n und K herstellen. Ein solcher Algorithmus heißt pseudopolynomiell und es muss die Eingabelänge der Werte einer beliebigen Instanz des 0/1 Rucksackproblems untersucht werden. Dazu müssen die Eingabewerte in Binärdarstellung umgewandelt und eine obere Schranke festlegt werden. Wir legen sozusagen die Eingabewerte auf das Band einer Turing-Maschine. Für das 0/1 Rucksackproblem besteht die Eingabe aus 2n+1 natürlichen Zahlen, also dem Gewicht (g_1,g_2,...,g_n), dem Wert (w_1,w_2,...,w_n), und der Gesamtkapazität K. Zusätzlich definieren wir einen Maximalwert \hat w = max\{w_1,w_2,...,w_n\}.

Die Beschränkung der Eingabelänge muss folgendermaßen aussehen:

\mathcal O(n\cdot(log_2 K+log_2 \hat w)+log_2 K) = \mathcal O(n\cdot(log_2 K+log_2 \hat w)).

Um nun die Rechenzeit des Algorithmus zu bestimmen, müssen wir eine Länge für K festlegen, z.B. K=2^n und damit \hat w \le 2^n. Daraus folgt, dass die Rechenzeit bei \mathcal O(n^2) liegt und der Algorithmus eine exponentielle Rechenzeit \mathcal O(n\cdot 2^n) hat.

In diesem Fall lässt sich die polynomiale Rechenzeit nur erreichen, wenn K durch ein Polynom beschränkt wird. So z.B. K \le n^{10}, was zu einer Rechenzeit von \mathcal O(n^{11}) führt. Eine solche Beschränkung ist jedoch unüblich, da die Größe und nicht die Bitlänge von K in die Laufzeit eingeht.

Rekursiver Algorithmus

Die Lösung des 0/1 Rucksackproblems mittels Rekursion wird im Folgenden mit einer Prozedur gezeigt, die im ersten Teil ohne memoizing und im zweiten Teil mit memoizing arbeitet.

Ohne Memoizing

Als erstes wird die Prozedur (Quelle: [1], S. 106) ohne memoizing implementiert. Die rekursive Definition kann leicht in die Prozedur überführt werden:

Durch die rekursiven Aurufe wird auch die Menge der zu lösenden Teilprobleme bestimmt. Deshalb kommt es in der Prozedur zu Mehrfachberechnungen. Um dies zu verhindern, wird das sogenannte memoizing eingesetzt. Bei dieser Technik wird vor der Berechnung eines neuen Wertes in der Tabelle nachgeschaut, ob dieser Wert bereits vorhanden ist. Wenn er vorhanden ist, wird er verwendet. Ist er nicht vorhanden, wird er berechnet und zur weiteren Verarbeitung in die Tabelle übernommen. Das wird am folgenden Beispiel gezeigt:

Mit Memoizing

Um die rekursive Prozedur (Quelle: [1], S. 107) mit memoizing zu implementieren, benötigt es nur wenige Änderungen im bereits vorhandenen Quellcode.

Als Résumé bleibt festzuhalten, dass die Ergebnisse mit denen der iterativen Prozedur übereinstimmen. Die rekursive Berechnung ohne memoizing ist selbstverständlich nicht tauglich, da durch die unnötige Mehrfachberechnung die Zahl der rekursiven Aufrufe viel zu hoch ist. Der memoizing- Methode wiederum sollte man den Vorzug vor der iterativen Methode geben, denn sie ist mindestens so schnell wie diese, ermöglicht eine direkte Ableitung der rekursiven Regeln und vermeidet die fehleranfällige Transformation in einen iterativen Bottom-up-Algorithmus.