Das Rucksackproblem
english

Ein Wanderer will verschiedene Gegenstände in seinen Rucksack packen. Jeder Gegenstand hat einen bestimmten Nutzen für ihn (z.B. einen Wert in €), sowie ein bestimmtes Gewicht und ein gegebenes Volumen. Leider hat der Rucksack nur eine begrenzte Gewichts- und Volumenkapazität. Welche Gegenstände soll der Wanderer in den Rucksack packen, so dass sein Inhalt bei Einhaltung der Kapazitätsgrenzen den maximalen Nutzen enthält?

Seien beispielsweise die Gegenstände A, B, C sowie die Kapazitätsgrenzen des Rucksacks gemäß folgender Tabelle gegeben.

Gegenstand
Volumen
(m3)
Gewicht
(kg)
Wert
(€)
A 6 3 10
B 3 28
C 1 12
Kapazität 8 5 -

Gegenstand A hat also ein Volumen von 6 m3, ein Gewicht von 3 kg und einen Wert von 10 €. Der Rucksack fasst maximal 8 m3 und 5 kg.

Mit Hilfe der Dynamischen Optimierung, einer Methode des Operations Research, löst man dieses Problem als ein mehrstufiges Entscheidungsproblem. Bei dem kleinen Beispiel findet man die Lösung aber auch durch Ausprobieren:

1 - 0 - 1     (zu lesen: nimm A, C),

bei einem Wert von 12 €. Drücken Sie den folgenden Startbutton, um ein beliebiges Rucksackproblem lösen zu lassen (Sie können die Anzahl der Gegenstände bestimmen, die Spaltenanzahl ist z.Zt. noch fix vorgegeben):

Falls Sie direkt über dieser Zeile nur eine graue Fläche sehen, jedoch keinen anklickbaren Button, so ist die Ursache, dass Sie nicht das neueste Java-Plug-In in Ihrem Browser installiert haben. Das Applet basiert auf den Java-2 Klassen (Swing), d.h. um es zu verwenden benötigen Sie die Java-Version 1.3 oder höher. Sie können das Plug-In bei SUN frei downloaden:

http://java.sun.com/getjava/download.html
oder
http://java.sun.com/products/plugin/


© de Vries 2002 federstrich Home