Quand le glouton se trompe
Exercice · OCaml (option informatique), chapitre 12 — Algorithmes gloutons
Énoncé
Comparer nb_pieces (glouton) et rendu_min (optimal) sur le système [4; 3; 1] et le montant 6, et expliquer.
Corrigé
nb_pieces [4;3;1] 6 : le glouton prend 4 (reste 2), puis 1 + 1 → 3 pièces. rendu_min [4;3;1] 6 : le minimum est 3 + 3 → 2 pièces. Le glouton échoue car son premier choix (la grosse pièce 4) bloque la meilleure combinaison. Sur un système non canonique, seule une méthode exhaustive (ou la programmation dynamique) garantit l'optimum. C'est la limite fondamentale du glouton.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.