Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Algorithme glouton:======
----

==== C'est quoi un algorithme glouton ? ====

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).

==== L'algorithme dans le cas Général ====

<code>
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
</code>

====Ci-dessous un exemple d'utilisation :====

=== Problème du voleur ===

^      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 :
  * 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).

======Implémentation en Python======
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é :
<code python>
#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))
</code>

=====Explication du programme :=====


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 :

<code python>
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) 
</code>


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 :[[les_fiches_revisions:structure_des_donnees:listes_piles_files | Listes, piles, files : structures linéaires. Dictionnaires, index et clé]]).

<code python>
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]
         }
</code>


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 :

<code python>
def rendu_monnaie(monnaie, somme_a_rendre):
    x = 1
    monnaie_used =[]
</code>


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.
<code python>
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)
</code>


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.
<code python>
if monnaie[x][0] >  somme_a_rendre:
        x += 1
                
else:
        somme_a_rendre -= monnaie[x][0]
        monnaie[x][1] += 1
</code>


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''.

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


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).
<code python>
print("")
return monnaie_used
</code>


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

<code python>
else:
        return "Le prix de l'objet est plus grand que l'argent donnée"
</code>


Permet simplement d'utilisé la fonction ''rendu_monnaie''.
<code python>
print(rendu_monnaie(monnaie, somme_a_rendre))
</code>

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

Outils pour utilisateurs

Outils du site

Outils de la page
