Rucksackprobleme

Bei den Rucksackproblemen handelt es sich um Optimierungsprobleme. Betrachtet werden dabei nicht-leere Mengen von n Objekten.
Jedes Objekt besitzt dabei zwei Kernattribute:

• einen Wert
• ein Gewicht

Als Begrenzung dient ein fest definierter Wert, die Kapazitätsbeschränkung K.

Gesucht ist die Menge derjenigen Objekte, die in der Summe einen maximalen Wert bei bestmöglicher Ausnutzung der Kapazität haben.

Beispiel

Ein LKW einer Spedition ist bis 50t belastbar. Es müssen einige Container transportiert werden:

• Container 1: Gewicht 10, Wert 60
• Container 2: Gewicht 20, Wert 100
• Container 3: Gewicht 30, Wert 120

Die Objektmenge besteht nun aus den folgenden Wertpaaren:

Die Kapazitätsbeschränkung K ist hier 50

Unterarten

0/1-Rucksackproblem (0-1 knapsack problem)

Ein Objekt wird immer komplett oder gar nicht in die Ergebnismenge übernommen

Bruchteil-Rucksack-Problem

Ein beliebiger Teil t (0% ≤ t ≤ 100%) jedes Gegenstands darf übernommen werden

Auf dieser Seite beschränken wir uns auf das 0/1-Rucksackproblem. Bruchteil-Rucksack-Probleme werden bei den Greedy-Algorithmen besprochen.

Ziel

In mathematischer Schreibweise sieht die oben genannte Zielstellung folgendermaßen aus:

Wobei folgendes gelten muss:

\sum_{i=1}^{n} x_{i}w_{i} \leq K, mit x_{i} \in {0, 1}

Teilmengen-Summen-Problem (subset-sum-problem)

Versuch einer Lösung

Aufzeigen der richtigen Lösung durch Probieren:

Tiefensuche

Breitensuche

Beschränkung des Suchbaumes

Nichtdeterminismus

Quellen

Literatur

Websites

Autoren

Ronny Lüttke mailto://s3roluet@stud.hs-zigr.de Paul Weinhold mailto://s3pawein@stud.hs-zigr.de