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.
L’autre caractéristiques des algorithmes gloutons est que lorsqu’un choix est fait, on tente de résoudre un problème plus petit. On appelle cela la progression descendante.
Prenons l’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 .
Puis implanter en code python .
Pour 423
Cliquez sur le lien pour tout comprendre !
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