L'algorithme Glouton est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape. Il existe d'autre algorithme plus optimiser que l'algorithme Glouton.

VARIABLE

x : un entier
l : une liste dans l'ordre croissant
r : une liste

DEBUT

ALGORITHME_GLOUTON(x, l) :
    compteur ← 1
    tant que x < 1 ou x > l:
        si l[compteur] > x:
            compteur ← compteur + 1
        sinon:
            x ← x - f[compteur]
            r.append(f[compteur])
            compteur ← compteur + 1
        fin si
    fin tant que
fin

Ci-dessous un exemple d'utilisation de celui-ci :

Le voleur à un sac avec une capacité de 30Kg.

Sachant que l'on cherche à maximiser le gain, commençons par établir un tableau nous donnant la “valeur massique” de chaque objet (pour chaque objet on divise sa valeur par sa masse) :

On classe ensuite les objets par ordre décroissant de valeur massique : A - C - B - D Enfin, on remplit le sac en prenant les objets dans l'ordre et en s'arrêtant dès que la masse limite est atteinte. C'est ici que ce fait “le choix glouton”, à chaque étape, on prend l'objet ayant le rapport “valeur-masse” le plus intéressant au vu des objectifs : 1re étape : A (13 Kg) 2e étape : C (13+8=21 Kg) 3e étape : B (13+8+12=33 Kg) ⇒ impossible, on dépasse les 30 Kg.

Le sac est donc composé de 2 objets : A et C pour un montant total de 1000 € et une masse totale de 21 Kg.

Voici un exemple de l'algorithme Glouton avec le problème du rendu de monnaie, ce code renvoie quelle(s) billet(s)/pièce(s) a été utilisé et combien de fois il l'a utilisé :

#initialisation des variables
prix = float(input("Prix: "))
client = float(input("Argent donné: "))
somme_a_rendre = client-prix 
 
#Pour éviter une erreur de conversion en binaire
somme_a_rendre = round(somme_a_rendre, 2) 
 
monnaie = {1 : [100, 0],
         2 : [50, 0],
         3 : [20, 0],
         4 : [10, 0],
         5 : [5, 0],
         6 : [2, 0],        
         7 : [1, 0],
         8 : [0.5, 0],
         9 : [0.2, 0],
         10 : [0.1, 0],
         11 : [0.05, 0],
         12 : [0.02, 0],
         13 : [0.01, 0]
         }
 
 
"""
Ce programme peut rencontrer des problèmes de calculs avec les décimaux,
car la fonction round arrondie au-dessus.
"""
def rendu_monnaie(monnaie, somme_a_rendre):
    x = 1
    monnaie_used =[]
    if somme_a_rendre > 0:
        while somme_a_rendre > 0:
 
            #Pour éviter une erreur de conversion en binaire
            somme_a_rendre=round(somme_a_rendre, 2)
 
            if monnaie[x][0] >  somme_a_rendre:
                x += 1
 
            else:
                somme_a_rendre -= monnaie[x][0]
                monnaie[x][1] += 1 
 
        for i in range(1, 13):
            if monnaie[i][1] >= 1:
                monnaie_used.append(monnaie[i])
        print("")
        return monnaie_used
    else:
        return "Le prix de l'objet est plus grand que l'argent donnée"
 
print(rendu_monnaie(monnaie, somme_a_rendre))

Le programme crée deux variables avec des input, et demande à l'utilisateur le prix de l'objet et l'argent donnée. Puis il fait la différence et arrondie au centième :

prix = float(input("Prix: "))
client = float(input("Argent donné: "))
somme_a_rendre = client-prix 
 
#Pour éviter une erreur de conversion en binaire
somme_a_rendre = round(somme_a_rendre, 2) 

Ensuite, la variable monnaie est un dictionnaire avec les clefs et leurs variables associées, soit la pièce ou le billet et son nombre d'utilisation (pour plus d'information sur les dictionnaires : Listes, piles, files : structures linéaires. Dictionnaires, index et clé).

monnaie = {1 : [100, 0],
         2 : [50, 0],
         3 : [20, 0],
         4 : [10, 0],
         5 : [5, 0],
         6 : [2, 0],        
         7 : [1, 0],
         8 : [0.5, 0],
         9 : [0.2, 0],
         10 : [0.1, 0],
         11 : [0.05, 0],
         12 : [0.02, 0],
         13 : [0.01, 0]
         }

Après avoir initialisée ces variables, le programme crée la fonction rendu_monnaie et initialise des variables locales, x étant la clef du dictionnaire et monnaie_used les valeurs des pièces/ billets utilisés :

def rendu_monnaie(monnaie, somme_a_rendre):
    x = 1
    monnaie_used =[]

Le programme vient ensuite vérifier si la variable somme_a_rendre est supérieur à 0 pour éviter une erreur. Ensuite une boucle basique, même chose qu'à l'initialisation initiale, un round pour arrondir au centième.

if somme_a_rendre > 0:
        while somme_a_rendre > 0:
 
            #Pour éviter une erreur de conversion en binaire
            somme_a_rendre=round(somme_a_rendre, 2)

Le programme vérifie le fait que la valeur de la pièce/billet qui correspondant à la clef soit supérieur à somme_a_rendre pour éviter que somme_a_rendre devienne négatif. Sinon le programme soustrait la pièce/billet correspondant à la clef à somme_a_rendre, puis ajoute 1 à deuxième variable de monnaie encore une fois avec la clef correspondant.

if monnaie[x][0] >  somme_a_rendre:
        x += 1
 
else:
        somme_a_rendre -= monnaie[x][0]
        monnaie[x][1] += 1

Le but de cette boucle for est de savoir quelle pièce/billet à été utilisé avec le if monnaie[i][1] >= 1 en vérifiant si la deuxième variable de la clef correspondante est supérieure ou égal à 1. Et si c'est le cas, alors le(s) billet(s)/pièce(s) utilisé(s) et le nombre de fois qu'ils ont été utilisé(s) sont ajoutés à monnaie_used.

for i in range(1, 13):
            if monnaie[i][1] >= 1:
                monnaie_used.append(monnaie[i])

Le print(“”) permet juste un saut de ligne pour de l'esthétique, et le programme renvoie les billet(s)/pièce(s) utilisé(s).

print("")
return monnaie_used

Ce else renvoie au if somme_a_rendre > 0 utilisé précédemment, dans le cas ou somme_a_rendre est inférieur à 0.

else:
        return "Le prix de l'objet est plus grand que l'argent donnée"

Permet simplement d'utilisé la fonction rendu_monnaie.

print(rendu_monnaie(monnaie, somme_a_rendre))

Les explications sont terminées j'espère qu'elles vous auront été utiles !