Dynamische Programmierung verständlich erklärt

Sie packen einen Koffer mit Gewichtsgrenze und wollen möglichst viel Nutzen mitnehmen. Alle Möglichkeiten durchzuprobieren dauert zu lange. Eine Tabelle kleiner Teilantworten findet die beste Auswahl, hat aber einen Haken. Diese Seite zeigt die Idee und den Haken.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Der Koffer mit der Gewichtsgrenze

Sie packen einen Koffer für eine Reise. Die Fluggesellschaft erlaubt höchstens 5 Kilo. Vier Dinge stehen zur Wahl. Jedes hat ein Gewicht und einen Nutzen, den Sie selbst in Punkten bewerten.

• Regenjacke: 2 Kilo, Nutzen 3 Punkte
• Buch: 3 Kilo, Nutzen 4 Punkte
• Kamera: 4 Kilo, Nutzen 5 Punkte
• Wanderschuhe: 5 Kilo, Nutzen 6 Punkte

Gesucht ist die Auswahl mit dem größten Gesamtnutzen, die zusammen nicht mehr als 5 Kilo wiegt. Jacke und Buch wiegen zusammen ebenfalls 5 Kilo und bringen 7 Punkte. Bei vier Dingen probieren Sie alle Kombinationen schnell durch.

Bei vielen Dingen geht das nicht mehr. Jedes Ding kommt mit oder bleibt zu Hause, und jedes weitere Ding stellt jede bisherige Kombination vor diese Wahl. Die Zahl der Kombinationen wächst so schnell, dass Durchprobieren bald zu lange dauert. Fachleute nennen diese Aufgabe das Rucksackproblem.

Die Idee: viele kleine Fragen

Stellen Sie statt einer großen viele kleine Fragen. Jede lautet: Was ist der größte Nutzen, wenn nur die ersten paar Dinge der Liste zur Wahl stehen und nur ein bestimmtes Gewicht erlaubt ist? Die Antworten tragen Sie in eine Tabelle ein. Jede Zeile steht für ein weiteres Ding, jede Spalte für ein erlaubtes Gewicht von null bis zur Grenze.

Die oberste Zeile gehört zu null Dingen und ist leicht: Der Nutzen ist null, gleich wie viel Gewicht erlaubt ist. Jede Zeile darunter folgt aus der Zeile über ihr und fügt ein Ding der Liste hinzu. Für das neue Ding gibt es nur zwei Möglichkeiten. Entweder es bleibt zu Hause, dann gilt die Antwort der Zeile darüber bei gleichem Gewicht. Oder es kommt mit, dann zählt sein Nutzen plus die Antwort der Zeile darüber für das Gewicht, das nach dem Einpacken noch übrig ist. Sie behalten das Bessere von beiden.

Die Tabelle von Hand ausfüllen

Füllen wir sie für den Koffer aus. Die Spalten sind die erlaubten Gewichte von null bis 5 Kilo, die Zeilen die Dinge in der Reihenfolge der Liste, unter der obersten Zeile ohne Ding. In der Jackenzeile steht null unter 2 Kilo, wo die Jacke nicht hineinpasst, und 3 ab 2 Kilo.

Nun das Buch, zunächst bei 3 Kilo Grenze. Ohne das Buch gilt die Antwort der Jackenzeile: 3 Punkte. Mit dem Buch zählen dessen 4 Punkte, mehr passt nicht hinein. Die Zelle steht auf 4. Bei 5 Kilo Grenze reichen die übrigen 2 Kilo nach dem Buch für die Jacke mit 3 Punkten. Die Zelle steht auf 7.

Kamera und Schuhe schlagen diese 7 Punkte nicht. In der letzten Zelle, unten rechts, steht damit der beste Gesamtnutzen: 7 Punkte.

Welche Dinge das sind, zeigt ein Gang rückwärts. Sie starten in der letzten Zelle (Wert 7) und prüfen die Dinge von unten nach oben. Sie rechnen: Nutzen des Dings plus Antwort der Zeile darüber für das Gewicht, das dann übrig bliebe. Ergibt das genau den Zellenwert, kommt das Ding mit.

Schuhe: 6 plus null ergibt nicht 7, also nein. Kamera: 5 plus null, nein. Buch: 4 plus 3 (die Jackenzeile bei 2 Kilo Rest) ergibt 7, also ja. Jacke: 3 plus null ergibt 3, genau den Wert der Jackenzeile bei 2 Kilo, also ja. Jacke und Buch kommen in den Koffer.

Warum das schnell ist

Jede kleine Frage wird genau einmal beantwortet und aufgeschrieben. Beim Durchprobieren käme dieselbe Teilfrage, etwa was Jacke und Buch zusammen bringen, in vielen Kombinationen vor. Die Tabelle merkt sich die Antwort und liest sie nach.

Die Arbeit wächst mit der Zahl der Zellen: Dinge mal erlaubte Gewichte. Dieses Vorgehen, kleine Fragen einmal zu beantworten und die Antworten wiederzuverwenden, heißt dynamische Programmierung.

Der Haken: die Breite der Tabelle

Die Tabelle hat eine Spalte für jedes erlaubte Gewicht, gezählt in der kleinsten Einheit, die vorkommt. Bei vollen Kilo sind es wenige Spalten. Gäben Sie dieselben vier Dinge auf das Gramm genau an, bekäme jedes Gramm eine eigene Spalte, und die Tabelle wäre entsprechend breiter, obwohl die Aufgabe dieselbe bleibt.

Zu dieser Seite gehört ein Programm zum Ausprobieren, das so etwas an erfundenen Zufallsfällen zeigt. Unter dem Text liegen zwei Knöpfe, der erste öffnet es. Zum Verstehen brauchen Sie es nicht. Die Aussagen ab hier beschreiben diese Beispielfälle, nicht die Wirklichkeit. Ein Fall hat nur sechs Dinge, deren Gewichte aber in winzigen Einheiten angegeben sind. Die Tabelle bräuchte mehr als zwei Millionen Zellen. Das Programm rechnet sie dann nicht. Eine halbe Tabelle hilft nicht: Jede Zeile kennt nur die Dinge bis dorthin, erst die letzte kennt alle.

Ein anderes Verfahren kommt mit solchen Zahlen zurecht. Es probiert Kombinationen der Reihe nach und gibt einen Zweig auf, sobald er nicht mehr gewinnen kann (Fachleute sagen Branch and Bound). Kennen Sie etwa Jacke und Buch mit 7 Punkten und fangen nun mit der Kamera an, bleibt 1 Kilo frei. Selbst mit einem teilbaren Ding ergäbe das weniger als 7 Punkte, also verfolgen Sie diesen Zweig nicht weiter. Solche Vergleiche ändern sich nicht, wenn man die Gewichte in kleineren Einheiten angibt. Das erklärt zum Teil, warum der Aufwand bei den sechs Dingen klein blieb. Mit sechs Dingen ist der Suchbaum ohnehin klein.

Auch dieses Verfahren hat eine Schwäche. Sind die nützlichsten Dinge zugleich die schwersten, wirken viele Kombinationen fast gleich gut, und es kann weniger Zweige aufgeben (eine Deutung dieser Seite). Im Mittel über 40 Zufallsfälle brauchte es bei 17 Dingen und kleinen Gewichten etwa 17 % mehr Schritte als bei voneinander unabhängigen Nutzen und Gewichten, bei größeren Gewichten im Mittel etwa das Neunfache. Der Tabelle ist das gleich: Ihre Größe hängt nur von der Zahl der Dinge und vom Gewichtslimit ab.

Häufige Missverständnisse

• „Eine Tabelle ist die bessere Lösung als Probieren.“ Beide Verfahren liefern das beste Ergebnis, das Probieren im Programm allerdings nur, solange es nicht wegen zu vieler Schritte abgebrochen wird. Ihre Schwächen sind verschieden: feine Gewichte für die Tabelle, ungünstige Aufgaben für das Probieren.
• „Die Tabelle schätzt und verbessert nach.“ Nein. Jede Zelle wird einmal aus ihren Vorgängerzellen ausgerechnet und ist dann die beste Antwort auf ihre Frage. Bei richtig ausgeführten Rechenschritten braucht das Ergebnis darum keine Gegenprobe.

Woran Sie das im Alltag erkennen

• Sie merken im Kopfrechnen, dass Sie dieselbe Zwischenrechnung mehrmals anstellen. Dann lohnt es sich, sie aufzuschreiben.
• Die Aufgabe lässt sich in Schritte zerlegen, in denen jede Antwort nur von früheren Antworten abhängt, etwa ein Urlaubsbudget, das Sie Tag für Tag verteilen.
• Die Zahlen sind klein und ganz, etwa volle Euro oder volle Kilo. Auf den Cent oder das Gramm genau wird eine Tabelle breit.

Was Sie mitnehmen

• Fragen Sie bei einer großen Auswahlaufgabe, ob sie sich in kleine, wiederverwendbare Fragen zerlegen lässt.
• Prüfen Sie vor dem Anlegen einer Tabelle, wie fein die Zahlen sind.
• Wer zwei Verfahren mit verschiedenen Schwächen kennt, wählt nach der Aufgabe statt nach Gewohnheit.

Wie ernst ist das Rechenbild zu nehmen?

Das Programm arbeitet mit einem vereinfachten Rechenbild: ganze Zahlen, zufällig erzeugte Fälle und ein einziges Gewichtslimit. Ob echte Aufgaben ähnliche Zahlenverhältnisse haben, hat es nicht untersucht. Der zweite Knopf unten führt zum zweiten Teil für Fachleute.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt das 0/1-Rucksackproblem, die Tabellenmethode und die Vergleichsgrößen der Demo.

• Problem: \(n\) Pakete mit ganzzahligen Gewichten \(w_i\) und Werten \(v_i\) sowie ein Gewichtslimit \(W\). Gesucht ist die Teilmenge mit dem größten Gesamtwert, deren Gesamtgewicht \(W\) nicht überschreitet. Jedes Paket wird ganz oder gar nicht genommen.
• Instanzen: zufällig erzeugt. Ein Regler stellt die Korrelation zwischen Wert und Gewicht ein (null: unabhängig; eins: Wert etwa gleich Gewicht plus Rauschen), ein zweiter das Limit als Anteil der Gewichtssumme, ein dritter die Größenordnung der Gewichte. Diese ist ein Faktor \(s\) (Stufen von eins über Zehnerpotenzen bis zehntausend sowie fünfzigtausend), der Gewichtsbereich und damit das Limit vervielfacht, ohne \(n\) zu ändern. Gewichte \(w_i\) sind ganzzahlig gleichverteilt zwischen fünf und dreißig, jeweils mal \(s\). Ein unabhängiger Wert \(u_i\) ist ganzzahlig gleichverteilt zwischen fünf und dreißig, ohne \(s\). Bei Korrelation \(\rho\) ist \(v_i = \max\big(1,\ \operatorname{round}((1-\rho)\,u_i + \rho\,(w_i + e_i))\big)\) mit Rauschen \(e_i\), ganzzahlig gleichverteilt zwischen minus acht und acht, ohne \(s\). Das Limit ist der gerundete Anteil der Gewichtssumme, mindestens eins.
• Tabellenmethode: von unten nach oben (Tabellierung). Zeile \(i\) gehört zu den ersten \(i\) Paketen, Spalte \(w\) zum Limit \(w\) von 0 bis \(W\). Eine zweite Phase liest die gewählten Pakete rückwärts aus der fertigen Tabelle ab. Das Optimum hängt nicht von der Reihenfolge der Pakete ab, denn Zielfunktion und Nebenbedingung sind Summen über alle Pakete.
• Vergleichsgröße: ein schlanker Branch & Bound. Er sortiert die Pakete nach Wert je Gewicht und verzweigt in dieser Reihenfolge je Paket auf „nehmen“ und „nicht nehmen“. Die Schranke eines Knotens ist sein bisheriger Wert plus die Füllung der übrigen Pakete in dieser Reihenfolge, wobei das erste nicht mehr passende anteilig genommen wird (Optimum der LP-Relaxierung, in der \(x_i\) beliebige Werte zwischen null und eins annehmen darf). Ein Kind entfällt, wenn es das Limit verletzt oder seine Schranke den besten bekannten Wert nicht übertrifft. Gezählt werden die Wurzel und jedes geprüfte Kind. Das Verfahren findet denselben Optimalwert, solange es nicht an einer festen Obergrenze der Knotenzahl (zweihunderttausend) abbricht; dann ist das Ergebnis zulässig, aber nicht als optimal bewiesen. Im Worst Case wächst der Aufwand exponentiell in \(n\); bei stark korrelierten Instanzen schneidet auch eine scharfe Schranke wenig ab. Ein Baum wird nicht gezeichnet.
• Sicherheitsgrenzen: Eine Tabelle mit mehr als 2.000.000 Zellen wird nicht berechnet. Die Demo nennt dann ihre Größe und lässt Branch & Bound für dieselbe Instanz laufen, denn solange die Tabelle nicht fertig ist, steht kein Optimum fest. Die Heatmap zeigt höchstens 300 Spalten als Stichprobe; unterhalb der Zellengrenze wird die volle Tabelle berechnet.

Die Formeln

Das Problem lautet:

\[\max \sum_{i=1}^n v_i x_i \quad \text{unter} \quad \sum_{i=1}^n w_i x_i \le W, \quad x_i \in \{0,1\}.\]

Die Tabelle \(\text{dp}[i][w]\) enthält den besten Wert aus den ersten \(i\) Paketen bei Limit \(w\). Ihre Rekursion:

\[\text{dp}[i][w] = \begin{cases} 0 & i = 0 \\ \text{dp}[i-1][w] & w_i > w \\ \max\big(\text{dp}[i-1][w],\ \text{dp}[i-1][w-w_i] + v_i\big) & \text{sonst} \end{cases}\]

Das Optimum steht in \(\text{dp}[n][W]\). Bei der Rückverfolgung gilt in der Zelle \(\text{dp}[i][w]\) mit \(i > 0\) Paket \(i\) genau dann als gewählt, wenn \(w \ge w_i\) und \(\text{dp}[i-1][w-w_i] + v_i = \text{dp}[i][w]\) ist. Sonst ist es ausgelassen, und man geht zu \(\text{dp}[i-1][w]\) weiter. Sind beide Möglichkeiten gleich gut, gilt es als gewählt. Es entsteht so eine von möglicherweise mehreren optimalen Auswahlen.

Der Aufwand ist \(O(n \cdot W)\) in Zeit und, solange die ganze Tabelle für die Rückverfolgung bleibt, auch in Speicher, genauer \((n+1)(W+1)\) Zellen. Für den Optimalwert allein genügt eine Zeile im Speicher. Er hängt von der Zahl \(W\) selbst ab, nicht von der Länge ihrer Kodierung: Das Verfahren ist pseudopolynomial.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.

Warum die Rekursion stimmt.

• Schritt 1: Jede zulässige Auswahl aus den ersten \(i\) Paketen enthält Paket \(i\) oder nicht.
• Schritt 2: Ohne Paket \(i\) ist sie eine zulässige Auswahl aus den ersten \(i-1\) Paketen bei Limit \(w\). Ihr bester Wert ist \(\text{dp}[i-1][w]\).
• Schritt 3: Mit Paket \(i\), was nur für \(w_i \le w\) möglich ist, bleibt eine zulässige Auswahl aus den ersten \(i-1\) Paketen bei Limit \(w-w_i\). Jede solche lässt sich um Paket \(i\) ergänzen. Der beste Wert ist \(\text{dp}[i-1][w-w_i] + v_i\).
• Schritt 4: Das Maximum beider Fälle ist \(\text{dp}[i][w]\). Mit der Basis \(\text{dp}[0][w] = 0\) folgt die Aussage durch Induktion über \(i\).

Warum der Aufwand pseudopolynomial ist und die Korrelation nicht eingeht.

• Schritt 1: Jede der \((n+1)(W+1)\) Zellen braucht eine Addition und einen Vergleich. Die Zeit ist daher proportional zu \(n \cdot W\).
• Schritt 2: Die Eingabe schreibt \(W\) mit etwa \(\log_2 W\) Bits. Ein Bit mehr erlaubt ein doppelt so großes \(W\) und damit eine doppelt so große Tabelle. Der Aufwand ist also polynomial in der Zahl \(W\), aber exponentiell in der Länge ihrer Binärschreibweise.
• Schritt 3: In \((n+1)(W+1)\) kommen die Werte \(v_i\) nicht vor, und die Korrelation wirkt nur auf sie. Bei gleichen Gewichten und gleichem Limit ist die Zellenzahl daher für jede Korrelation dieselbe.

Warum Branch & Bound dieselbe Instanz in größeren Einheiten nicht anders behandelt.

• Schritt 1: Die Sortierung nach \(v_i/w_i\) und die Schranke vergleichen nur Verhältnisse und Summen. Werden alle \(w_i\) und \(W\) mit demselben Faktor \(s\) multipliziert, bleiben Reihenfolge, anteilig gefüllter Wert und alle Vergleiche dieselben. Die Knotenzahl derselben Instanz ändert sich nicht, während die Zellenzahl mit \(s\) wächst.
• Schritt 2: Der Regler der Demo erzeugt bei neuer Größenordnung aber neue Zufallsgewichte, keine skalierte Kopie. Die Aussage gilt darum nur im Mittel. Eine Nachrechnung dieser Seite mit vierzig Zufallsinstanzen zu je sechs Paketen (Korrelation null, Limit die halbe Gewichtssumme) ergab über alle Größenordnungen des Reglers eine praktisch gleiche mittlere Knotenzahl, während die mittlere Zellenzahl im selben Verhältnis wuchs wie die Größenordnung. Ab der Größenordnung zehntausend lag in allen vierzig Fällen die Tabelle über der Zellengrenze, bei der Größenordnung tausend in keinem.

Durchgerechnetes Beispiel

Eine Kleinstinstanz mit vier Paketen: Gewichte 2, 3, 4, 5, Werte 3, 4, 5, 6, Limit 5. Ihr Optimum, Wert 7, wird in der Demo als von Hand nachgerechnet geprüft. Die Zellen unten sind eine Rechnung dieser Seite.

Die Tabelle, Zeile für Zeile, jeweils für die Limits \(w = 0\) bis \(w = 5\):

• Zeile 0 (kein Paket): Wert 0 bei jedem Limit.
• Zeile 1 (Gewicht 2, Wert 3): Wert 0 bei \(w = 0\) und \(w = 1\), Wert 3 bei \(w = 2\) bis \(w = 5\).
• Zeile 2 (Gewicht 3, Wert 4): \(\text{dp}[2][w]\) = 0; 0; 3; 4; 4; 7.
• Zeile 3 (Gewicht 4, Wert 5): \(\text{dp}[3][w]\) = 0; 0; 3; 4; 5; 7.
• Zeile 4 (Gewicht 5, Wert 6): \(\text{dp}[4][w]\) = 0; 0; 3; 4; 5; 7.

Die Zelle \(\text{dp}[2][5]\) ist \(\max(\text{dp}[1][5],\ \text{dp}[1][2] + 4) = \max(3,\ 3 + 4) = 7\). Rückverfolgung ab \(\text{dp}[4][5] = 7\): Paket 4 würde \(\text{dp}[3][0] + 6 = 6\) ergeben, nicht 7, also ausgelassen. Paket 3 würde \(\text{dp}[2][1] + 5 = 5\) ergeben, ausgelassen. Paket 2 ergibt \(\text{dp}[1][2] + 4 = 7\), gewählt, weiter bei Limit 2. Paket 1 ergibt \(\text{dp}[0][0] + 3 = 3 = \text{dp}[1][2]\), gewählt. Die Auswahl ist Paket 1 und 2 mit Gewicht 5 und Wert 7. Paket 4 allein hätte Gewicht 5 und nur Wert 6.

Befunde

Die Zahlen stammen aus Messungen der Demo, die Voraussetzung steht jeweils dabei.

Frage	Befund
Hängt die Zellenzahl der Tabelle von der Korrelation ab?	Nein. Bei 17 Paketen füllt die Tabelle mit starker Korrelation (Wert nahe am Gewicht) dieselbe Zellenzahl wie mit Korrelation null, bei gleichen Gewichten und gleichem Limit.
Wie viele Knoten braucht Branch & Bound mit starker Korrelation gegenüber Korrelation null?	Gemessen am Verhältnis der mittleren Knotenzahlen über 40 Zufallsinstanzen mit 17 Paketen (die Paketzahl der Beispielinstanz mit starker Korrelation): bei kleinen Gewichten etwa 17 % mehr Knoten, bei Gewichten der Größenordnung 10 im Mittel etwa das Neunfache.
Was geschieht bei wenigen Paketen und riesigem Limit?	Bei 6 Paketen (Beispielinstanz mit riesigem Limit) und um den Faktor zehntausend vergrößerten Gewichten überschreitet die Tabelle 2.000.000 Zellen und wird nicht berechnet. Branch & Bound bleibt winzig.
Stimmen die Optimalwerte überein?	In den Prüfungen ja: gegen vollständige Enumeration kleiner Zufallsinstanzen (auch mit vergrößerten Gewichten), gegen einen eigenständigen Branch & Bound und gegen die Kleinstinstanz oben, jeweils ohne Abbruch durch die Knotenobergrenze. Die Rückverfolgung nennt jedes Paket genau einmal und ist mit der gemeldeten Auswahl konsistent.

Grenzen und was die Messung zeigt

• Instanzfamilie: Alle Befunde gelten für die zufälligen Instanzen dieser Familie, nicht für reale Datensätze. Die Mittelwerte zur Korrelation gelten für 17 Pakete; einzelne Instanzen können in die Gegenrichtung ausfallen, und für andere Paketzahlen ist nichts gemessen.
• Verschiedene Einheiten: Zellen und Knoten sind keine gleichen Arbeitsschritte. Die Demo stellt sie nebeneinander, misst aber keine Laufzeit.
• Größenordnung und Korrelation vermischt: Bei positiver Korrelation sind die Werte an die vergrößerten Gewichte gekoppelt, das Rauschen aber nicht. Das Rauschen wird relativ kleiner. Der Mehraufwand von Branch & Bound bei Größenordnung 10 ist daher nicht allein eine Wirkung der Zahlengröße; diese Deutung ist eine Vermutung dieser Seite, nicht gemessen.
• Schwache Referenz: Der Branch & Bound ist eine schlanke Vergleichsgröße mit einer einfachen Schranke, nicht auf Geschwindigkeit ausgelegt. Andere Schranken oder Verzweigungsregeln könnten andere Knotenzahlen ergeben. Die Obergrenze der Knotenzahl wurde in einer Rechnung dieser Seite mit achtzehn Paketen, starker Korrelation und neunhundert Zufallsfällen genau einmal erreicht; dort ist der gemeldete Wert nicht als optimal bewiesen.
• Zwischenstand: Nach Zeile \(i\) kennt man den besten Wert aus den ersten \(i\) Paketen, aber nicht das Optimum aller Pakete. Bevor die letzte Zeile fertig ist, steht keine Aussage über den Abstand zum Optimum fest.
• Nicht gezeigt: Speichersparende Varianten, mehrere Nebenbedingungen und Rucksackvarianten ohne Obergrenze je Paket. Rundet man die Werte und legt die Tabelle über die Werte statt über die Gewichte an (kleinstes Gewicht je erreichbarem Wert), entsteht ein Näherungsverfahren, das für jede vorgegebene Genauigkeit eine Güte garantiert (aus dem Gedächtnis, nicht geprüft). Rundet man nur die Werte der gewichtsindizierten Tabelle der Demo, schrumpft sie nicht.

Quellen

• Richard Bellman: Dynamic Programming. Princeton University Press, 1957.
• Hans Kellerer, Ulrich Pferschy, David Pisinger: Knapsack Problems. Springer, 2004.
• Oscar H. Ibarra, Chul E. Kim: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM 22 (1975).

Die Demo nennt keine Literatur. Die Angaben stammen aus dem Gedächtnis und sind nicht geprüft. Alle Zahlen im Text stammen aus der Demo, Rechnungen dieser Seite sind als solche gekennzeichnet.