Das Rucksackproblem

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

(m³)

Gewicht

(kg)

Wert

(€)

Kapazität

Gegenstand A hat also ein Volumen von 6 m³, ein Gewicht von 3 kg und einen Wert von 10 €. Der Rucksack fasst maximal 8 m³ 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/