Das Rucksackproblem (englisch Knapsack Problem) ist eines der berühmtesten Probleme der Kombinatorik: Ein Rucksack fasst höchstens das Gewicht W, und es stehen n Gegenstände mit Gewichten w₁, ..., wₙ und Werten v₁, ..., vₙ zur Verfügung. Gesucht ist eine Auswahl, deren Gesamtwert maximal ist, ohne die Kapazität zu überschreiten. Die Entscheidungsvariante („gibt es eine Auswahl mit Wert ≥ k?") ist NP-vollständig — das Problem ist damit ein Paradebeispiel dafür, wie einfach formulierte Fragen trotzdem schwer sein können.
0/1, gebrochen und unbeschränkt
- 0/1-Rucksack: Jeder Gegenstand wird höchstens einmal genommen — die klassische, NP-schwere Variante.
- Gebrochener Rucksack: Gegenstände sind teilbar (etwa Mehl oder Sand). Hier liefert der Greedy-Algorithmus nach Wertdichte v/w das optimale Ergebnis.
- Unbeschränkter Rucksack: Jeder Gegenstand darf beliebig oft verwendet werden.
Pseudo-polynomiale Lösung per dynamischer Programmierung
Das 0/1-Problem lässt sich mit dynamischer Programmierung in O(n·W) lösen: Eine Tabelle speichert für jede Kapazität und jeden Gegenstand den besten erreichbaren Wert. Das ist pseudo-polynomial — die Laufzeit hängt vom Zahlenwert der Kapazität W ab, nicht von ihrer Bitlänge. Ein Rucksack mit Kapazität 10¹⁰ ist damit genauso aussichtslos wie ein großes n, und solange P ≠ NP gilt, gibt es keinen polynomialen Algorithmus für alle Instanzen.
Approximation und Praxis
Ein einfacher Greedy nach Wertdichte kann beim 0/1-Problem beliebig schlecht abschneiden; kombiniert man ihn mit dem besten einzelnen Gegenstand, erhält man eine Garantie von 50 Prozent des Optimums. Durch Skalierung der Werte entsteht ein FPTAS: eine (1−ε)-Approximation in polynomialer Zeit für jedes feste ε. In der Praxis lösen Metaheuristiken wie Simulated Annealing, Genetische Algorithmen oder der Ameisenalgorithmus auch große Instanzen gut.
Anwendungen
- Ladungs- und Containerplanung: Was kommt bei begrenztem Ladevolumen an Bord?
- Budget- und Investitionsentscheidungen: Welche Projekte bei begrenztem Kapital?
- Subset-Sum-Spezialfall: Ist eine Teilmenge mit exakter vorgegebener Summe möglich?
- Als Baustein in komplexeren Verfahren, etwa beim Travelling Salesman Problem oder in der ganzzahligen Optimierung, wo es das einfachste 0/1-ILP ist.
Verwandte Grundlagen: Dynamische Programmierung, Greedy-Algorithmus, NP-Vollständigkeit, Ganzzahlige Optimierung, Approximationsalgorithmus.