Ceci est une ancienne révision du document !
L'algorithme Glouton
est une méthode d'optimisation qui consiste à prendre la meilleure solution à chaque étape. De ce fait, le résultat final n'est pas toujours le plus optimisé.
VARIABLE x : un entier f : une liste dans l'ordre croissant 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
Objet | A | B | C | D |
---|---|---|---|---|
Masse | 13Kg | 12Kg | 8Kg | 10Kg |
Valeur marchande | 700€ | 400€ | 300€ | 300€ |
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) :
Objet | A | B | C | D |
---|---|---|---|---|
Valeur Massique | 54 €/Kg | 33 €/Kg | 38 €/Kg | 30 €/Kg |
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 :
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 !