Algorithme glouton python – Exemple rendu de monnaie

Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c'est le cas.

Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c’est le cas.

Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c'est le cas.

Algorithme glouton : Introduction

Le problème du rendu de monnaie est formulé de la façon suivante. Comment rendre une somme donnée avec un minimum de pièces et billets  ?

Voici un exemple en python de la résolution du problème :

Si on considère le système monétaire Euro sans les centimes on a l’ensemble

EURO = (1, 2, 5, 10, 20, 50, 100, 200, 500)

Algorithme glouton rendu de monnaie python

Maintenant, pour rendre la monnaie sur une valeur x de en utilisant ces pièces et billets, alors nous vérifierons le premier élément du tableau. Et si il est supérieur à x, nous passons à l’élément suivant. Sinon le gardons. Maintenant, après avoir pris une pièce ou un billet de valeur issu du tableau de pieceEtBillet [i], la valeur totale x que nous devons faire deviendra x – pieceEtBillet [i].

Voici l’algorithme glouton python associé :

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(33)#Exemple sur 33 euros

La sortie pour 33 euro est alors :

20
10
2
1

Autre exemple avec 55 euro d’algorithme glouton python :

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(55)#Exemple sur 55 euros

La sortie est alors :

50
5

Conclusion

Le problème du rendu de monnaie est NP-difficile relativement au nombre de pièce et billet du système monétaire considéré (euro dans cet exemple). Pour aller plus loin on pourra démontrer que pour certains systèmes de monnaie dits canoniques, l’utilisation d’un algorithme glouton est optimal. Un système monétaire est dit canonique si pour toute somme s l’algorithme glouton conduit à une décomposition minimale.

La difficulté NP est la propriété déterminante d’une classe de problèmes informellement “au moins aussi difficiles que les problèmes les plus difficiles de NP”.

Un exemple simple de problème NP-hard est le problème de somme de sous-ensembles. Si P est différent de NP alors il est peu probable de trouver un algorithme en temps polynomial qui résout de façon exact ce problème.

Liens externes

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Liens internes

https://128mots.com/index.php/category/python/

https://128mots.com/index.php/category/non-classe/

Laisser un commentaire

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