Systematische Suche WS13-14
Inhaltsverzeichnis |
Rucksackprobleme
Aus einer Menge von Gegenständen die einen Wert w und ein Gewicht g besitzen, gilt es einen Rucksack zu füllen bei dem der Gesamtwert der eingepackten Gegenstände maximal ist, ohne die Kapizitätsgrenze K des Rucksacks zu überschreiten.
Allgemein beschreiben Rucksackprobleme: Beladungsprobleme, Verschnittprobleme oder Probleme der Budgetkontrolle.
Beispiel
Thomas will sein Geld anlegen und versucht ein Investment-Portfolio zu erstellen, aus dem er sich maximalen Gewinn erhofft. Er hat 10000€ (K) zur Verfügung und will diese in unterschiedliche Aktien verteilen, welche eine Bewertung (w) und einen festen zu investierenden Wert (g) besitzen. Nun geht es darum ein Portfolio zusammenzustellen (Rucksack), in welchem die Gesamtbewertung aller gekauften Aktien maximal ist, dabei darf sein Budget nicht überzogen werden.
Zur Verfügung stehende Aktien:
| Aktie | Wert (in €) | Bewertung (0-10, höher ist besser) |
| Mapple | 2500 | 8 |
| Minisoft | 3000 | 4 |
| Le-Nogo | 5000 | 5 |
| Wogitech | 6000 | 3 |
| Joogle | 4000 | 7 |
Varianten
Es gibt viele unterschiedliche Formen des Rucksackproblems:
- 0/1 Rucksackproblem:
Hier wird ein Gegenstand entweder vollständig (1) oder gar nicht (0) eingepackt. Außerdem darf der selbe Gegenstand nur einmal eingepackt werden. - Bruchteil-Rucksackproblem:
Man kann einen beliebigen Teil t, mit 0\% \le t \le 100\%, eines Gegenstandes einpacken. - Unbeschränktes Rucksackproblem:
Bei dieser Variante des Problems gibt es keine Kapazitätsobergrenze, d.h. K = \infty. - Teilmengen-Summen-Problem (subset-sum problem):
In diesem speziellen Fall geht es darum die Gewichtskapazität des Rucksacks optimal auszunutzen, da der Wert mit dem Gewicht übereinstimmt, d.h. g_i = w_i für alle i.
In diesem Artikel wird ausschließlich das 0/1 Rucksackproblem betrachtet. Bruchteil-Rucksackprobleme werden im Artikel der Greedy-Algorithmen behandelt.
Lösungsverfahren
Intuitives Verfahren
Tiefensuche
Das Tiefe-zuerst-Suchverfahren (engl. depth first search) oder kurz: die Tiefensuche stellt ein Lösungsverfahren für das oben benannte Rucksackproblem dar.
Voraussetzung:
Vorgehensweise: