Retour

Algorithmes gloutons

Principe

Les algorithmes gloutons sont souvent utilisés pour résoudre ces problèmes d'optimisation. Pour trouver une solution optimale on procède par étapes :

• On effectue le meilleur choix possible à chaque étape de l'algorithme,
• il n'y a pas de retour en arrière : lorsqu'un choix est fait, il n'est pas modifié par la suite.
• On se retrouve donc à chaque étape, avec un problème de plus en plus petit à résoudre.

Attention toutefois, cette méthode ne fournit pas systématiquement la solution optimale au problème proposé.

Implémentation en Python

1. Rendu de monnaie

🐍 Script Python

def rendu_de_monnaie(systeme: list, somme: float)->list :
    monnaie = []
    # Travail en centimes (pour eviter les erreurs de calcul avec les flottants)
    systeme.reverse() # Pour inverser l'ordre des termes d'une liste
    systeme = [piece*100 for piece in systeme] 
    somme_restante = somme * 100   

    i = 0                               # initialisation de l'indice du terme de systeme qui va être ajouté à la liste monnaie
    while somme_restante > 0:
        if somme_restante < systeme[i]: # cas où la valeur monétaire est trop grande
            i = i + 1                   # on considère la valeu suivante (qui sera inférieure)
        else :                          # systeme[i] est la plus grande valeur monétaire possible inférieure à somme_restante
            somme_restante = somme_restante - systeme[i]
            monnaie.append(systeme[i])


    return [piece/100 for piece in monnaie]

somme=2.63
systeme = [0.01, 0.02, 0.05, 0.10, 0.20, 1, 2]

print(rendu_de_monnaie(systeme, somme))