Rendu de monnaire
Algo 10
Résumé du cours
Le problème du rendu de monnaie est un problème d’optimisation qui consiste à rendre la monnaie avec le moins de pièces possibles.
Pour une somme relativement faible, le nombre de combinaisons possibles est très grand. Une solution approchée est souvent un compromis suffisant.
L’approche gloutonne consiste à effectuer un choix optimal à chaque étape et ne pas revenir dessus.
Par exemple pour le rendu de monnaie, l’approche gloutonne conssiste à rendre la plus grande pièce possible à chaque étape.
Remarque
L’approche gloutonne ne donne pas systématiquement la meilleure solution. Cependant la rapidité d’exécution de ce type d’algorithme compense souvent cet inconvénient.