Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Rucksackproblem 
(nach Breier, N.: Grenzen des Computereinsatzes. Teil 1. In LogIn 10 (1990) Heft 3 und Herms, A.: Genetische Algorithmen. Teil 1: Das Rucksackproblem. In LogIn Nr. 125 (2004), S. 59ff)


Grundproblem und Beispiel

Ein Rucksack soll mit einer Auswahl von n Gegenständen unterschiedlichen Gewichts und Werts gefüllt werden. Wie muss die Auswahl getroffen werden, damit das Gesamtgewicht ein Grenzgewicht nicht überschreitet und der Gesamtwert möglichst hoch ist? 

Um einen Algorithmus zu finden, wird das Problem zunächst mathematisiert:

Gegeben seien natürliche Zahlen a1, a2, ..., an (Gewichte) und w1, w2, ..., wn (Werte) sowie ein Grenzgewicht g. 
Gesucht sind Zahlen x1, x2, ..., xn mit xk = 0 oder xk = 1 und x1·a1 + x2·a2 + ... + xn·an ≤ g und x1·w1 + x2·w2 + ... + xn·wn max.
Dabei bedeutet xk = 1, dass der Gegenstand eingepackt wird.

Beispiel:

10 Gegenstände stehen für einen Rucksack zur Verfügung. Die Gegenstände haben ein Gewicht von a = (3, 7, 4, 12, 8, 10, 9, 14, 10, 12) und einen Wert w = (3, 5, 2, 11, 4, 6, 2, 15, 12, 9). Der Rucksack kann maximal 60 kg tragen. Eine mögliche Lösung könnte das Einpacken der Gegenstände 3, 12, 8, 9, 14 und 12 sein, da das Gewicht dann 58 kg beträgt und der Wert des Rucksacks 44 beträgt. Man notiert die Gegenstände als Vektor x = (1, 0, 0, 1, 1, 0, 1, 1, 0, 1).

exakte Lösung

Eine offensichtliche Lösung besteht darin, alle möglichen Kombinationen der Gewichte zu erzeugen und dabei zu prüfen, ob das maximale Gewicht überschritten wird. Außerdem wird der Wert gespeichert und aus allen in Frage kommenden Kandidaten der günstigste gewählt

Laufzeitanalyse und Ordnung des Algorithmus:

Die Erzeugung aller möglichen Gewichts-Vektoren benötigt eine Zeitordnung von O(2n), denn der Vektor entspricht einer Dualzahl aus n Dualziffern. Mit anderen Worten: dieser Algorithmus ist für größere n ungeeignet!

Ein polynomialer Algorithmus

Wenn hier ein polynomialer Algorithmus für das Rucksackproblem stehen würde, so könnte ich mich auf die faule Haut legen und eine Menge Geld verdienen. Es gibt bis zum heutigen Tage keinen solchen Algorithmus. Man sagt auch: das Rucksackproblem ist NP-vollständig und meint damit, dass es zu den schwierigsten Problemen der Informatik gehört (siehe Kapitel P-NP-Problem)

Näherungslösungen

Da man nicht unendlich viel Zeit hat und Rucksackprobleme durchaus praxisrelevant sind, müssen Algorithmen entwickelt werden, die das Problem näherungsweise lösen können.

Eine mögliche Variante zeigt die folgende Visualisierung.



zur Startseite
© Tino Hempel 1997 - 2005 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.