L'algorithme Glouton est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape sans revenir sur ses décisions. De ce fait, le résultat final n'est pas toujours le plus optimisé.

Pour sa complexité, si les objets sont déjà triés par ordre décroissant de valeur, alors la boucle bornée de 1 à n correspond à une complexité de l'ordre de O(n). Par contre si la liste des objets n'est pas triée on passe à une compléxité de l'ordre de O(n logn).

VARIABLE

x : un entier
f : une liste ordonnée 
r : une liste

DEBUT

ALGORITHME_GLOUTON(x, l) :
    compteur ← 1
    tant que x > 0:
        si f[compteur] > x:
            compteur ← compteur + 1
        sinon:
            x ← x - f[compteur]
            ajouter(f[compteur], r)
            compteur ← compteur + 1
        fin si
    fin tant que
FIN

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.

On remarque que ce n'est pas la combinaison la plus optimisé, celle-ci serait A,B (1100€ pour 25Kg) et non A,C (1000€ pour 21Kg).

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 !