Programmierung » ClassPad 300 » Basic » Allgemeines/Spezielles Rucksackproblem

Allgemeines/Spezielles Rucksackproblem

Man stelle sich vor man sei ein Bankräuber und ist erfolgreich in eine Bank eingebrochen. Man hat auch schon den gößten Rucksack mit, den man finden konnte, aber der ist immer noch zu klein, um alle Dinge mitzunehmen.
Wie geht man nun vor? Vielleicht einfach soviel einpacken, bis der Rucksack voll ist, ungeachtet des Wertes der Objekte, die man einpackt? Oder nur die Wertvollsten Objekte mitnehmen?

Keiner würde das so machen... Und laut Murphys Gesetz schleppt man sich fast zu Tode und hat am Ende sowieso nur vergleichsweise wertlosen Plunder mitgenommen... Doch zum Glück gibt es da Leute die sich darüber schon Gedanken gemacht haben (auch wenn nicht direkt über diesen Fall) und man kann die Lösung für das Problem einen Computer oder einen Taschenrechner überlassen.

Das Allgemeine Rucksackproblem

Man hat folgende Vorraussetzungen:
1. Einen Rucksack mit einer maximalen Tragkraft gmax.
2. n Objekte mit einem Gewicht und einem Wert.
3. Jedes Objekt kann beliebig oft in den Rucksack gepackt werden, jedoch darf die Tragkraft des Rucksacks nicht überschritten werden.

Ziel ist es nun den Rucksack optimal zu packen. D.h. den maximalen Wert bei maximaler Auslastung des Rucksacks zu erreichen. Zur Lösung kann man folgende Formel verwenden:
f(i,j) = max(f(i - 1, j), f(i, j - g(i)) + w(i)); f(0, j) = 0; f(i, 0) = 0
f(i,j) - Erreichter Wert unter Verwendung der ersten i Objekte und der Tragkraft j
g(i) - Gewicht des i-ten Objektes
w(i) - Wert des i-ten Objektes

Die Werte dieser Rekursion werden bis i <= n und j <=gmax berechnet. Das erreichbare Maximum ist dann f(n, gmax). Um nun die Objekte für Optimale Packung des Rucksacks herauszufinden, geht man die Tabelle von diesen Wert entsprechend folgender Regeln ab:
1. Wenn die Werte von der Zelle (i, j) und (i - 1, j) ungleich sind, dann gehe g(i) nach links. Das Objekt i gehört zur Lösung. 2. Wenn die Werte von der Zelle (i, j) und (i - 1, j) gleich sind, ist zu prüfen, ob das Objekt i noch in den Rucksack hineinpasst und der maximale Wert errreicht werden kann. Wenn ja, dann gehe nach links und nehme Objekt i in die Lösung auf. Wenn nein, dann gehe nach oben, das Objekt gehört nicht zur Lösung. 3. Es wird solange nach den ersten beiden Punkten verfahren, bis man bei i = 0 oder j = 0 angekommen ist.

Wenn man alle Lösungen für das Problem sucht, dann muss man bei Punkt 2 abzweigen und einmal den Weg mit und einmal den Weg ohne das Objekt i verfolgen.

Beispiel:

Objekt	1	2	3	4	5
Gewicht	1	2	2	3	4
Wert	3	7	6	11	15

Mit gmax=9 wird folgende Tabelle erzeugt:

	j
i

Der Weg zur Lösung (4,4,4) ist markiert.

Spezielles Rucksackproblem

Dieses Problem ist dem Allgemeinen Rucksackproblem gleich, jedoch mit dem Unterschied, das jedes Objekt nur jeweils höchstens einmal eingepackt werden darf.
Mit dieser Einschränkung ändert sich die Formel wie folgt:
f(i,j) = max(f(i - 1, j), f(i - 1, j - g(i)) + w(i)); f(0, j) = 0; f(i, 0) = 0
f(i,j) - Erreichter Wert unter Verwendung der ersten i Objekte und der Tragkraft j
g(i) - Gewicht des i-ten Objektes
w(i) - Wert des i-ten Objektes

Auch muss nun immer, wenn ein Objekt zur Lösung hinzugenommen wurde eine Zeile nach oben gegangen werden, da es nur einmal zur Lösung beitragen kann.

Das Beispiel von oben mit gmax=8:

	j
i

Der Weg zur Lösung (5,4,1) ist markiert.

Probleme

Der Aufwand zur Lösung des Allgemeinen/Speziellen Rucksackproblems steigt sehr stark mit wachsender Anzahl an Objekten und Tragkraft des Rucksacks. Deshalb sollte man nicht alzu große Werte verwenden. Auch lässt der verwendete Algorithmus nur positive ganze Zahlen als Gewicht zu.

MCS-Datei mit dem Programm (Version 1)