On remplit un sac à dos de capacité 8 avec des objets choisis parmi quatre objets de (poids, valeur) (2, 3), (3, 4), (4, 5) et (5, 6). Il n'existe qu'un exemplaire de chaque objet, et les objets ne peuvent pas être fractionnés. Quelle est la valeur totale maximale pour un poids total de 8 ou moins ?

Réponse : C. 10

Choisir les objets de poids 3 et 5 donne un poids de 8 et une valeur de 4 + 6 = 10, qui est le maximum. Les poids 2 et 5 (valeur 9) ou 3 et 4 (valeur 9) tiennent aussi, mais restent en dessous de 10, et trois objets quelconques pèsent au moins 2 + 3 + 4 = 9, au-delà de la capacité. Un algorithme glouton qui place les objets par ordre de valeur par unité de poids prend les objets de poids 2 et 3 (valeur 7), puis plus aucun objet ne tient dans la capacité restante de 3 : il s'arrête donc à 7. La programmation dynamique met à jour, objet par objet, une table de la meilleure valeur atteignable pour chaque capacité c, et trouve l'optimum en O(nW) pour n objets et une capacité W.