Algorithmes gloutons, problème du rendu de monnaie

Au programme

Algorithmique

Introduction

Les algorithmes gloutons forment une catégorie d’algorithmes permettant de parvenir à une solution pour un problème d’optimisation qui vise à maximiser/minimiser une quantité (plus court chemin (GPS), plus petite durée d’exécution, meilleure organisation d’un emploi du temps, etc.)

Le problème du rendu de monnaie

Énoncé

Vous êtes commerçant et devez rendre de la monnaie à vos clients de façon optimale , c’est-à-dire avec le nombre minimal de pièces et de billets ¹.

• On suppose que les clients ne vous donnent que des sommes entières en euros (pas de centimes pour simplifier) ;
• Les valeurs des pièces et billets à votre disposition sont : 1, 2, 5, 10, 20, 50, 100, 200 et 500. On suppose que vous avez autant d’exemplaires que nécessaire de chaque pièce et billet ;
• Dans la suite, afin de simplifier, nous désignerons par « pièces » à la fois les pièces et les billets.

Stratégie gloutonne

Un client nous achète un objet qui coûte 53 euros. Il paye avec un billet de 200 euros. On doit donc lui rendre 147 euros. Une façon de lui rendre la monnaie est de le faire avec un billet de 100, deux billets de 20, un billet de 5 et une pièce de 2.

Pour minimiser le nombre de pièces à rendre, il apparaît la stratégie suivante :

• On commence par rendre la pièce de plus grande valeur possible ;
• On déduit cette valeur de la somme (encore) à rendre ;
• On recommence, jusqu’à obtenir une somme nulle.

En procédant ainsi, on se rend compte que l’on résout le problème étape par étape et qu’un choix optimal est fait à chaque étape (la pièce de plus grande valeur ). Cette stratégie entre donc bien dans la catégorie des algorithmes gloutons .

Implémentation en Python

Le corrigé se trouve à cette adresse : https://repl.it/@dlatreyte/rendudemonnaie.

1. Importer le module typing au début du fichier :

1

from typing import List

1. Préparer la fonction main suivante et étudier sa structure :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def main():
    # valeurs des pièces
    pieces = [1, 2, 5, 10, 20, 50, 100]

    prix = int(input("Quel est le prix ? "))
    client = int(input("Combien le client donne-t-il ? "))

    a_rendre = somme_a_rendre(prix, client)
    comment = pieces_a_rendre(a_rendre, pieces)

    reponse = ["{} piece(s) de {}".format(comment[i], pieces[i]) for i in 
   range(len(pieces))]
    print("Je dois rendre : {}".format(a_rendre))
    print("Je donne donc : {}".format(reponse))

1. Définir la fonction somme_a_rendre dont la spécification est :

1
2
3
4
5

def somme_a_rendre(prix: int, montant_client: int) -> int:
    """
    Détermine la somme à rendre à partir du prix et du montant donné par
    le client.
    """

1. Définir la fonction pieces_a_rendre dont la spécification est :

1
2
3
4
5
6
7

def pieces_a_rendre(somme: int, pieces: List[int]) -> List[int]:
    """
    Détermine les pièces (et leur nombre) à choisir pour rendre la somme
    passée en argument.
    Utilise la division euclidienne et le modulo de façon à pouvoir
    traiter tous les cas.
    """

1. Appeler la fonction main.

Un algorithme glouton conduit-il toujours à la solution optimale ?

Voici quelques exercices pour répondre à cette question.

Exercice 1 (Plus court chemin)

• On part du point $O$.
• On veut atteindre en parcourant la distance la plus petite possible tous les points : $A$, $B$, $C$, $D$, $E$ et $F$.
• L’ordre de parcours des points n’a pas d’importance.

1. Tracer le chemin à suivre en adoptant une stratégie gloutonne.
2. La stratégie gloutonne est-elle la meilleure ? Si tel n’est pas le cas, tracer le chemin optimal.

Remarque : On peut montrer (ce n’est pas facile) que l’algorithme glouton retourne la solution optimale globale pour le rendu de monnaie… à la condition d’utiliser un système de monnaie tel que l’euro.

Un algorithme glouton conduit-il toujours à une solution ?

Pourquoi se contenter d’une stratégie gloutonne ?

Comme nous le verrons dans le document Chap. 23,02, la stratégie gloutonne est utilisée dans le cas où la complexité des algorithmes donnant à coup sûr la réponse correcte est exponentielle (pour le problème du sac à dos, $O (n) = 2^n$). De tels algorithmes sont très souvent inexploitables.

Code Python du programme principal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

<p>&quot;&quot;&quot;
Mise en œuvre de la stratégie gloutonne pour le
problème du rendu de monnaie.
&quot;&quot;&quot;
from typing import List</p>
<p>def somme_a_rendre(prix: int, client: int) -&gt; int:
&quot;&quot;&quot;
Détermine la somme à rendre à partir du prix et du montant donné par
le client.
&quot;&quot;&quot;
return client - prix</p>
<p>def pieces_a_rendre(somme: int, pieces: List[int]) -&gt; List[int]:
&quot;&quot;&quot;
Détermine les pièces (et leur nombre) à choisir pour rendre la somme
passée en argument.
Utilise la division euclidienne et le modulo de façon à pouvoir
traiter tous les cas.
&quot;&quot;&quot;
a_rendre = []
indice_piece = len(pieces) - 1
while indice_piece &gt;= 0:
rendu = somme // pieces[indice_piece]
encore_a_rendre = somme % pieces[indice_piece]
a_rendre.insert(0, rendu)
somme = encore_a_rendre
indice_piece -= 1
return a_rendre</p>
<p>def main():
# valeurs des pièces
pieces = [1, 2, 5, 10, 20, 50, 100]</p>
<pre><code>prix = int(input(&quot;Quel est le prix ? &quot;))
client = int(input(&quot;Combien le client donne-t-il ? &quot;))

a_rendre = somme_a_rendre(prix, client)
comment = pieces_a_rendre(a_rendre, pieces)

reponse = [&quot;{} piece(s) de {}&quot;.format(comment[i], pieces[i]) for i in range(len(pieces))]
print(&quot;Je dois rendre : {}&quot;.format(a_rendre))
print(&quot;Je donne donc : {}&quot;.format(reponse))
</code></pre>
<p>main()</p>

Suggestions de lecture :

• Langages et programmation