Algorithmes gloutons

Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l’espoir d’obtenir un résultat optimum global.

Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l’algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton.

system_euro=[500,200,100,50,20,10,5,2,1]
def rendu_monnaie(somme,systeme):
    liste_pieces=[]
    for valeur in systeme:
        while somme>=valeur:
            liste_pieces.append(valeur)
            somme=somme-valeur
    return liste_pieces