Ein Rucksack mit der Kapazität 8 wird mit Gegenständen aus vier Gegenständen mit (Gewicht, Wert) (2, 3), (3, 4), (4, 5) und (5, 6) gefüllt. Jeden Gegenstand gibt es nur einmal, und Gegenstände lassen sich nicht teilen. Wie groß ist der höchste Gesamtwert bei einem Gesamtgewicht von höchstens 8?

Antwort: C. 10

Die Gegenstände mit den Gewichten 3 und 5 ergeben das Gewicht 8 und den Wert 4 + 6 = 10, das Maximum. Die Gewichte 2 und 5 (Wert 9) oder 3 und 4 (Wert 9) passen ebenfalls, erreichen aber nicht 10, und drei beliebige Gegenstände wiegen mindestens 2 + 3 + 4 = 9, mehr als die Kapazität. Ein Greedy-Algorithmus, der die Gegenstände nach Wert pro Gewichtseinheit einpackt, nimmt die Gegenstände mit den Gewichten 2 und 3 (Wert 7); danach passt kein Gegenstand mehr in die verbleibende Kapazität 3, und er bleibt bei 7 stehen. Die dynamische Programmierung aktualisiert Gegenstand für Gegenstand eine Tabelle des besten Werts, der innerhalb jeder Kapazität c erreichbar ist, und findet das Optimum in O(nW) für n Gegenstände und die Kapazität W.