Algorithmes gloutons

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.

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

É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

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *