Les algorithmes gloutons sont utilisés dans des problèmes d’optimisation. Un problème d’optimisation consiste à déterminer les valeurs des paramètres permettant de :
- minimiser ou maximiser une fonction objectif ;
- satisfaire une ou des fonctions contraintes (il existe des problèmes avec ou sans contrainte).
Ils correspondent à une solution optimale obtenue en effectuant une suite de meilleurs choix pour chaque étape de l’algorithme (à chaque étape, on fait le milleur choix possible).
Il n’y a pas de retour en arrière : quand un choix est fait à une étape, il n’est pas modifié ultérieurement et il ne modifie pas les choix précédents.
Autre caractéristique des algorithmes gloutons : lorsqu’un choix est fait, on tente de résoudre un problème plus petit. On appelle cela la progression descendante.
Exemple du rendu de monnaie :
Le problème du rendu de monnaie est un problème d’algorithmique qui s’énonce de la façon suivante : étant donné un système de monnaie, comment rendre une somme donnée de façon optimale, c’est-à-dire avec le nombre minimal de pièces et billets ?
Dans la zone euro, le système en vigueur, en mettant de côté les centimes d’euros, met à disposition des pièces ou billets de : 1€, 2€, 5€, 10€, 20€, 50€, 100€, 200€, 500€.
On suppose que nous avons à notre disposition un nombre illimité de ces pièces ou billets.
Vous devez rendre 423€
donne une solution sans programmation :
- on prend une valeur
- tant que la somme est supérieure à la valeur, on ajoute la valeur à la liste liste_pieces
- la somme est alors égale à la somme moins la valeur
- etc, jusqu’à obtenir la liste_pieces que l’on renvoie
Écrire un algorithme en pseudo-code
Implémenter l’algorithme en python
On pourra écrire une fonction rendu_monnaie(somme, systeme) qui prend en entrée la somme à rendre et le système de monnaie contenant les valeurs des pièces et billets et qui renvoie la liste des billets et pièces.
Par exemple rendu_monnaie(97, systeme_euro) doit renvoyer la liste [50, 20, 20, 5, 2]).
L’idée est la suivante : on rend la monnaie avec le plus grand billet, tant que l’on peut, puis on essaye avec le suivante, puis la suivante… Il y a une boucle for et, dans celle-ci, une boucle while.
system_euro=[500,200,100,50,20,10,5,2,1]
def rendu_monnaie(somme,systeme):
liste_pieces=[]
for valeur in systeme:
while somme>=valeur:
liste_pieces.append(valeur)
somme=somme-valeur
return liste_pieces
Aucune réponse