Knapsack 0/1 Rechner (Rucksackproblem)

Rechner Rucksackproblem 0/1, fraktional und bounded: dynamische Programmierung, Greedy, Effizienzvergleich Wert/Gewicht und Rekonstruktion der Lösung.

Berechnungsparameter
War dieser Rechner nützlich?

Das Rucksackproblem

Das Rucksackproblem (knapsack) ist eines der 21 ursprünglichen NP-vollständigen Probleme von Karp (1972) und ein Eckpfeiler der kombinatorischen Optimierung. Gegeben eine Sammlung von Objekten mit Gewicht und Wert und ein Rucksack der Kapazität W, bestimme die Teilmenge mit maximalem Gesamtwert ohne Überschreitung. Hauptvarianten: 0/1 (Objekt ganz oder ausgeschlossen), fraktional (Bruchteile erlaubt), bounded (begrenzte Kopien).

Mathematische Formulierung

Maximiere Sigma v_i * x_i unter Sigma w_i * x_i <= W, mit x_i in {0,1} für 0/1, x_i in [0,1] für fraktional, x_i in {0,1,...,q_i} für bounded. Die Entscheidungsvariante ist NP-vollständig; die Optimierung ist NP-schwer. Pseudo-polynomiale O(nW) Algorithmen existieren via dynamische Programmierung.

Dynamische Programmierung

Der klassische Algorithmus baut dp[i][w] = maximaler Wert mit ersten i Objekten und Kapazität w. Rekurrenz: dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + v_i) falls w_i <= w. Basis dp[0][w] = 0. Optimallösung dp[n][W]; Objekte durch Backtracking. Komplexität O(nW) Zeit, reduzierbar auf O(W) Platz.

Die vier Modi

  1. 0/1 lösen: dynamische Programmierung mit Rekonstruktion.
  2. Fraktional: Greedy sortiert nach v/w absteigend.
  3. Bounded: binäre Zerlegung reduziert auf 0/1.
  4. Effizienzvergleich: Wert/Gewicht-Verhältnisse.

Greedy scheitert bei 0/1

Sortieren nach v/w absteigend löst fraktional, kann aber für 0/1 beliebig suboptimal sein. Beispiel: W=10, Objekte [(6,60), (5,50), (5,50)]. Greedy wählt das erste (Ratio 10), lässt W=4 ungenutzt: Wert 60. Optimum nimmt die letzten zwei: Wert 100.

Approximation FPTAS

Es existiert ein voll polynomielles Approximationsschema (FPTAS) für 0/1 Knapsack: für jedes epsilon>0, Algorithmus in O(n^3/epsilon) mit Wert >= (1-epsilon) * OPT. Erreicht durch Skalierung der Werte mit v_max*epsilon/n und DP über Werte.

Klassisches Beispiel

W=10, Objekte (2,3), (3,4), (4,5), (5,6). DP ergibt dp[4][10] = 13 mit Objekten 1, 2, 4 (Gewichte 2+3+5=10, Werte 3+4+6=13).

Anwendungen

  • Budgetzuweisung: Projektwahl mit maximalem ROI.
  • Cutting Stock: Optimierung bei Textil-, Papier-, Metallschnitt.
  • Portfoliooptimierung: Titelauswahl mit Kapitalgrenze.
  • Containerbeladung: See- und Luftlogistik.
  • Cloud-Ressourcenzuweisung: VM-Platzierung mit RAM/CPU-Grenzen.

Geschichte des Rucksackproblems

Das Rucksackproblem (englisch knapsack) hat seinen Namen von der anschaulichen Situation, in der jemand einen Rucksack begrenzter Kapazität füllen muss, indem er aus vielen Gegenständen jene mit maximalem Gesamtwert auswählt. In der Mitte des 20. Jahrhunderts im Operations Research formalisiert, wurde es zu einem der meistuntersuchten Probleme der theoretischen Informatik. 1972 nahm Richard Karp es in seine berühmte Liste von 21 NP-vollständigen Problemen auf und besiegelte damit seine grundlegende Schwierigkeit. Das Problem spielte auch in der Kryptografie eine historische Rolle: 1978 schlugen Ralph Merkle und Martin Hellman eines der ersten Public-Key-Kryptosysteme vor, das auf dem Rucksack beruhte (das Merkle-Hellman-Knapsack). Die Idee war, die Schwierigkeit des Problems als Sicherheitsgarantie zu nutzen, doch das System wurde 1982 von Adi Shamir spektakulär gebrochen, der seine besondere Struktur ausnutzte. Seither bleibt der Rucksack ein grundlegender Prüfstein für exakte, heuristische und Approximationsalgorithmen.

Warum der Algorithmus pseudopolynomiell ist

Die dynamische Programmierung löst das 0/1-Rucksackproblem in Zeit O(n·W), wobei n die Anzahl der Gegenstände und W die Kapazität ist. Auf den ersten Blick scheint das effizient, doch es gibt ein feines Detail: W ist ein Zahlenwert, nicht die Größe der Eingabe. Zur Darstellung der Kapazität W genügen etwa log₂(W) Bit, sodass die Zeit O(n·W) exponentiell in der Länge der Eingabedaten ist. Das ist mit einem pseudopolynomiellen Algorithmus gemeint: polynomiell im Wert der Zahlen, aber exponentiell in der Anzahl der Ziffern. Deshalb ist der Rucksack schwach NP-schwer: bleiben Kapazitäten und Gewichte klein, ist die DP sehr schnell, doch mit riesigen Zahlen (Hunderte von Ziffern) wird sie unpraktikabel. Ein wirklich in der Eingabegröße polynomieller Algorithmus ist nicht bekannt, und seine Existenz käme dem Beweis von P = NP gleich.

Aktualisiert im Juli 2026

Häufig gestellte Fragen

Warum ist Knapsack 0/1 NP-schwer, wenn DP O(nW) ist?

Weil O(n·W) pseudopolynomiell ist, nicht polynomiell. W ist ein Zahlenwert, der mit etwa log₂(W) Bit dargestellt wird, sodass die Zeit im Verhältnis zur tatsächlichen Eingabelänge exponentiell ist. Mit kleinen Gewichten und Kapazitäten ist die DP sehr schnell, doch haben die Zahlen Hunderte von Ziffern, wird sie unpraktikabel. Die NP-Schwere des Rucksacks ist gerade deshalb schwach, weil sie an die Größe der Zahlen gebunden ist, nicht an die Anzahl der Gegenstände.

Wann DP und wann Greedy verwenden?

Die dynamische Programmierung liefert die exakte optimale Lösung des 0/1-Problems, kostet aber O(n·W): sie lohnt sich bei mäßiger Kapazität. Der Greedy-Ansatz nach Wert/Gewicht ist sehr schnell (O(n log n)), liefert das Optimum aber nur beim fraktionalen Rucksack, wo die Gegenstände teilbar sind. Beim 0/1-Problem kann Greedy stark danebenliegen. Greedy verwendet man nur für schnelle Schätzungen oder als Starheuristik.

Wie funktioniert die binäre Zerlegung für bounded?

Beim bounded-Problem hat jeder Gegenstand eine maximal verfügbare Menge. Statt ihn vielfach zu duplizieren, zerlegt man ihn in Gruppen der Größe 1, 2, 4, 8, ... (Zweierpotenzen) plus einen Rest. Mit diesen Paketen lässt sich jede Menge bis zum Maximum zusammensetzen, und das Problem reduziert sich auf einen 0/1-Rucksack mit log(Qmax) zusätzlichen Gegenständen pro Artikel. So sinkt der Aufwand von O(n·W·Qmax) auf O(n·W·log Qmax), ein enormer Gewinn.

Gibt es einen besseren Algorithmus als O(nW)?

Für den allgemeinen Fall ist kein in der Eingabegröße polynomieller Algorithmus bekannt, und einen zu finden würde P = NP beweisen. Es gibt jedoch vollständig polynomielle Approximationsschemata (FPTAS), die bei Akzeptanz eines kleinen relativen Fehlers ε eine Lösung innerhalb (1−ε) des Optimums in Zeit polynomiell in n und 1/ε garantieren. In der Praxis nutzt man auch Branch-and-Bound-Algorithmen, die mit oberen Schranken große Instanzen viel schneller als der schlimmste Fall lösen.

Ist das mehrdimensionale Knapsack viel schwerer?

Ja. Beim mehrdimensionalen Knapsack hat jeder Gegenstand mehrere Kostenattribute (Gewicht, Volumen usw.) und es sind mehrere Kapazitätsbeschränkungen gleichzeitig einzuhalten. Die dynamische Programmierung bräuchte eine Tabelle mit einer Dimension pro Beschränkung, was Speicher und Zeit explodieren lässt. Das Problem bleibt NP-schwer und lässt kein einfaches FPTAS mehr zu: in der Praxis geht man es mit ganzzahliger linearer Programmierung, Metaheuristiken oder ausgefeilten Branch-and-Bound-Algorithmen an.

Wie teilbare Objekte in der Praxis behandeln?

Sind die Gegenstände teilbar, wechselt man zum fraktionalen Rucksack, der optimal mit einem einfachen Greedy gelöst wird: man sortiert die Gegenstände nach absteigendem Wert/Gewicht-Verhältnis und füllt den Rucksack mit den effizientesten zuerst, indem man einen Bruchteil des letzten nimmt, um die Kapazität genau auszuschöpfen. Das ist der typische Fall stetiger Materialien wie Flüssigkeiten, Pulver oder schmelzbarer Edelmetalle, und anders als im 0/1-Fall ist Greedy hier streng optimal.

Reduziert sich Knapsack auf SUBSET-SUM?

SUBSET-SUM ist ein Sonderfall des Rucksacks, bei dem der Wert jedes Gegenstands gleich seinem Gewicht ist und man fragt, ob eine Teilmenge genau die Kapazität erreicht. Es ist selbst NP-vollständig, und seine Reduktion auf den Rucksack zeigt dessen Schwierigkeit. Beide teilen dieselbe pseudopolynomielle Struktur: die DP auf SUBSET-SUM kostet O(n·S), wobei S die Zielsumme ist, mit derselben Anwendbarkeitsgrenze wie der Rucksack.

Wofür wird das Rucksackproblem in der Praxis verwendet?

Es ist überall bei Problemen der optimalen Zuteilung begrenzter Ressourcen: bei der Auswahl von Investitionen unter festem Budget (Capital Budgeting), beim Zuschnitt von Materialien zur Abfallminimierung, beim Beladen von Containern und Flugzeugen, in der Produktionsplanung und bei der Projektauswahl. Es erscheint auch in der historischen Kryptografie, in der Speicherverwaltung und in Empfehlungssystemen, überall dort, wo ein Wert unter einer Kapazitätsbeschränkung zu maximieren ist.

Kommentare (0)

Noch keine Kommentare. Sei der Erste!