Een knapzak met capaciteit 8 wordt gevuld met voorwerpen gekozen uit vier voorwerpen met (gewicht, waarde) (2, 3), (3, 4), (4, 5) en (5, 6). Van elk voorwerp is er maar één, en voorwerpen kunnen niet worden gesplitst. Wat is de maximale totale waarde bij een totaal gewicht van hoogstens 8?

Antwoord: C. 10

De voorwerpen met gewicht 3 en 5 geven gewicht 8 en waarde 4 + 6 = 10, en dat is het maximum. Gewichten 2 en 5 (waarde 9) of 3 en 4 (waarde 9) passen ook, maar halen 10 niet, en drie voorwerpen wegen minstens 2 + 3 + 4 = 9, meer dan de capaciteit. Een gretig algoritme dat voorwerpen in volgorde van waarde per gewichtseenheid inpakt, neemt de voorwerpen met gewicht 2 en 3 (waarde 7); daarna past geen voorwerp meer in de resterende capaciteit van 3, dus het stopt bij 7. Dynamisch programmeren werkt per voorwerp een tabel bij met de beste waarde die binnen elke capaciteit c haalbaar is, en vindt het optimum in O(nW) voor n voorwerpen en capaciteit W.