On paie 8 yens avec des pièces de 1 yen, 4 yens et 6 yens. Quelle affirmation relie correctement le nombre de pièces choisi par un algorithme glouton, qui utilise d'abord autant que possible la plus grosse pièce, et le nombre minimal de pièces ?

Réponse : B. L'algorithme glouton utilise 3 pièces et manque le minimum de 2

L'algorithme glouton prend d'abord une pièce de 6 yens et paie les 2 yens restants avec deux pièces de 1 yen, soit 3 pièces. Or deux pièces de 4 yens suffisent pour payer avec seulement 2 pièces. Comme un algorithme glouton ne fait qu'accumuler le choix qui paraît le meilleur à chaque instant, il n'est pas optimal pour certains systèmes de pièces. La programmation dynamique, qui remplit dans l'ordre croissant une table du nombre minimal de pièces pour chaque montant de 0 à 8 yens, trouve toujours le minimum. Pour des systèmes de pièces comme celui du Japon (1, 5, 10, 50, 100 et 500 yens), l'algorithme glouton donne toujours le minimum.