Informatikmaterialien
von Tino Hempel
Startseite | Informatik | Physik | Mathematik | Sonstiges |
| |
Informatikmaterialien |
Startseite | Informatik | Physik | Mathematik | Sonstiges | |
 |
Richard-Wossidlo-Gymnasium Ribnitz-Damgarten |
|---|
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).
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)
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. |