OCaml (option informatique) · Chapitre 12 · Exercice de TD
Quand le glouton se trompe
Algorithmes gloutons · niveau 3 (difficile)
É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.
Exercices semblables
- Sélection d'activités corrigé
- Nombre maximal d'activités corrigé
- Rendu optimal exhaustif corrigé
- Sac à dos fractionnaire corrigé
- Nombre minimal de salles corrigé