Definition
Das Rucksackproblem (international auch als Knapsack-Problem bekannt) ist ein modellhaftes kombinatorisches Optimierungsproblem, das allgemein so aussieht:
Man hat einen Rucksack mit einer maximalen Traglast (in kg) sowie eine Anzahl von Gegenständen mit Gewichten (in kg) und Werten (in Euro).
Man soll die optimale Kombination von Gegenständen (mit dem höchsten Gesamtwert) finden, die Traglast darf dabei nicht überschritten werden.
Beispiel
Beispiel: Rucksack eines Einbrechers
Wir stellen uns für ein Beispiel einen Einbrecher im Juweliergeschäft vor:
Die maximale Traglast des Rucksacks sei 10 kg.
Der Einbrecher hat 5 Gegenstände im Visier:
- 5 kg-Goldbarren, Wert 100.000 €
- 7-kg-Silberbarren, Wert 60.000 €
- 3 kg-Platinbarren, Wert 80.000 €
- Geldkassette, wiegt 4 kg, Inhalt: 90.000 €
- Schmuckschatulle, wiegt 2 kg, Wert 60.000 €
Was soll der Einbrecher einpacken, damit seine Beute möglichst hoch, die Traglast des Rucksacks aber nicht überschritten wird? (sonst reißt dieser bei der Flucht und alles ist verloren.)
In diesem einfachen Beispiel "sieht" man die Lösung einigermaßen schnell (Computer / Programme können aber nicht sehen, sie brauchen einen Algorithmus, der dann auch bei mehr Gegenständen funktioniert).
Die optimale Lösung lautet: Goldbarren (5 kg) + Platinbarren (3 kg) + Schmuckschatulle (2 kg) – genau 10 kg (Traglast voll ausgeschöpft), Gesamtwert: 240.000 €.
Bei 5 Gegenständen gibt es 25 = 32 mögliche Teilmengen – einige davon überschreiten jedoch sofort das Gewichtslimit von 10 kg und sind damit ungültig.
Lösungsmöglichkeiten
Es gibt mehrere Möglichkeiten, das Rucksackproblem zu lösen:
- vollständige Aufzählung aller möglichen Kombinationen (das können Millionen sein);
- Branch-and-Bound-Verfahren;
- dynamische Programmierung.
Das Rucksackproblem ist wie gesagt ein Modell; es geht nicht wirklich darum, Rucksäcke zu packen, sondern um andere, v.a. ökonomische Fragen.
Fazit
- Das Rucksackproblem optimiert die Auswahl von Gegenständen mit Gewicht und Wert so, dass der Gesamtwert maximiert wird, ohne eine Kapazitätsgrenze zu überschreiten.
- Es gehört zur kombinatorischen Optimierung; die Anzahl möglicher Teilmengen wächst exponentiell mit der Gegenstandszahl (2n).
- Lösungsansätze: vollständige Enumeration (optimal, aber langsam), Branch-and-Bound, dynamische Programmierung, Greedy-Heuristiken.
- Praktische Anwendungen: Projektauswahl bei Budgetbeschränkung, Portfolio-Optimierung, Frachtplanung.
Selbsttest: Rucksackproblem
Aufgabe: Rucksackproblem lösen
Ein Unternehmen hat ein Investitionsbudget von 10 Mio. € und kann aus drei Projekten wählen:
| Projekt | Investition | Erwarteter Gewinn |
|---|---|---|
| P1 | 4 Mio. € | 9 Mio. € |
| P2 | 6 Mio. € | 12 Mio. € |
| P3 | 3 Mio. € | 7 Mio. € |
Jedes Projekt wird entweder vollständig durchgeführt oder gar nicht (ganzzahlig).
- Ermitteln Sie durch vollständige Enumeration alle zulässigen Kombinationen.
- Welche Kombination maximiert den Gesamtgewinn?
Lösung
1. Vollständige Enumeration (Budget ≤ 10 Mio. €):
| Kombination | Invest | Gewinn | Zulässig? |
|---|---|---|---|
| P1 | 4 | 9 | ✓ |
| P2 | 6 | 12 | ✓ |
| P3 | 3 | 7 | ✓ |
| P1 + P2 | 10 | 21 | ✓ |
| P1 + P3 | 7 | 16 | ✓ |
| P2 + P3 | 9 | 19 | ✓ |
| P1 + P2 + P3 | 13 | 28 | ✗ (>10) |
2. Optimale Auswahl: P1 + P2 mit Investition 10 Mio. € und maximalem Gewinn von 21 Mio. €.