Le rendu de monnaie

Dans ce problème, un commerçant (ou un distributeur ou une caisse automatique) doit rendre la monnaie à un client en utilisant un minimum de pièces (nous appelerons pièces les pièces ou les billets pour simplifier). Il a pour cela à sa disposition une quantité indéfinie de pièces de 1, 2, 5, 10, 20, 50, 100 euros.

Exemple : il doit rendre 42 euros. Pour cela, il peut rendre :

42 pièces de 1 € ;
1 pièce de 20 €, 2 pièces de 10 €, 2 pièces de 1 € ;
etc.

Bien sûr, le deuxième choix est ici meilleur que le premier (5 pièces contre 42 pièces).

Attention

Ici, il peut y avoir plusieurs pièces de même montant dans le rendu (dans le problème du sac à dos, on ne pouvait pas mettre deux fois un objet dans le sac !).

Exercice 2

Le commerçant va rendre une pièce à la fois, d'une valeur qu'il va choisir suivant un critère de choix qui lui semble optimal (méthode gloutonne).

A votre avis, quel est le meilleur critère de choix ?
Appliquez la méthode gloutonne avec une somme de 73 €.
A votre avis, cette méthode gloutonne donne-t-elle la réponse optimale au problème ?

Système canonique⚓︎

Le système de pièces {1, 2, 5, 10, 20, 50, 100} est dit canonique car il permet d'obtenir une solution optimale avec l'algorithme glouton.

Par contre, supposons qu'il n'y ait plus de pièces de 5 € et de 10 €, le rendu de 63 € ne sera pas optimal avec la méthode gloutonne qui donne 50 + 6 × 2 + 1 donc 8 pièces, alors que 3 × 20 + 2 + 1 font 5 pièces.
Le système de pièces {1, 2, 20, 50, 100} n'est donc pas canonique.

D’autres systèmes ne sont pas canoniques, par exemple le système britannique d'avant 1971 était constitué des pièces {1, 2, 6, 12, 24, 30, 60, 240} (en livres Sterling £). Avec l’algorithme glouton, la somme de 48 £ est rendue avec 30 + 12 + 6, soit 3 pièces alors que la solution optimale est 24 + 24, soit 2 pièces.

Plus génant, avec le système {2, 5, 10, 20}, pour une somme de 26 :

l'algorithme glouton choisit 20 (il reste donc 6) puis 5 (il reste donc 1) donc la somme rendue est 25 au lieu de 26...
il existait pourtant une solution : 20 + 3 × 2.

Pas de solution

Moralité : une méthode gloutonne peut, dans des cas mal étudiés (ici c'est le système qui est défaillant), ne pas donner de solution du tout.

Recherche exhaustive⚓︎

Dans des systèmes non canoniques, l'algorithme glouton ne donne pas forcément la solution optimale. Pour en trouver une, il pourrait être tentant de faire la liste de toutes les décompositions d'une somme dans le système de monnaie configuré.

Contrairement au problème du sac à dos, le nombre de décompositions d'une somme m n'est pas facile à écrire mais un simple programme donne ces résultats :

pour m = 10 £ : 9 rendus possibles en 0.0005 seconde
pour m = 50 £ : 319 rendus possibles en 0.009 seconde
pour m = 100 £ : 2856 rendus possibles en 0.107 seconde
pour m = 500 £ : 2170207 rendus possibles en 180.84 secondes
pour m = 1000 £ : 68663175 rendus possibles en 7702.27 secondes
au vu de ces résultats, on peut estimer qu'il faudrait environ 120 jours pour m = 10000 £ et plus de 1500 ans pour m = 100000 £ (je n'ai pas vérifié...).

On le voit, cette recherche exhaustive devient vite trop gourmande en temps...

Algorithme glouton pour le rendu de monnaie⚓︎

Voici une première description de l'algorithme :

en entrée :
- la somme à rendre s'appelle somme (doit être positive) ;
- la liste des pièces disponibles s'appelle systeme_monetaire (doit être triée par ordre croissant) ;
en sortie : la liste des pièces à rendre s'appelera liste_pieces_a_rendre

Tant que je n'ai pas fini de rendre la monnaie :

je regarde la plus grande valeur de pièce : 100 € et tant que je peux rendre des pièces de 100 € (tant que la somme restant dûe est supérieure à 100), je le fais ;
puis je passe à la valeur inférieure : 50 € et tant que je peux rendre des pièces de 50 € (tant que la somme restant dûe est supérieure à 50), je le fais ;
etc.

Remarque : voici deux représentations possibles d'une réponse, par exemple avec une somme de 39 € :

soit avec un tableau des valeurs des pièces rendues : [20, 10, 5, 2, 2] ;
soit avec un tableau indiquant le nombre de pièces de chaque sorte dans le rendu : [0, 2, 1, 1, 1, 0, 0] car il y a 0 pièce de 1 €, 2 pièces de 2 €, 1 pièce de 5 €, 1 pièce de 10 €, 1 pièce de 20 €, 0 pièce de 50 € et 0 pièce de 100 €.

Le programme mis en place dépendra de la représentation choisie.

Exercice 3

Voici une écriture plus précise d'un algorithme glouton pour le problème du rendu de la monnaie :

📋 Texte

liste_pieces_a_rendre ← liste vide  
restant ← somme  
ind ← indice de la pièce de plus grande valeur dans `systeme_monetaire`  
Tant que restant n'est pas nulle  
Faire  
    valeur_piece ← systeme_monetaire[ind]  
    Tant que restant >= valeur_piece  
    Faire  
        Ajouter valeur_piece au tableau liste_pieces_a_rendre  
        restant ← restant - valeur_piece  
    Fin Tantque  
    ind ← ind - 1

Traduisez cet algorithme en Python et testez-le dans Thonny avec systeme_monetaire qui vaut [1, 2, 5, 10, 20, 50, 100] ou [1, 2, 6, 12, 24, 30, 60, 240] et quelques monnaies à rendre.

Exercice 3bis (pour les plus rapides)

Nous pouvons aussi lister les nombres de pièces de chaque sorte : par exemple [0, 2, 1, 1, 1, 0, 0] représente 39 dans le système [1, 2, 5, 10, 20, 50, 100].

Nous obtenir ces nombres, nous pouvons faire des soustractions mais aussi des divisions entières, par exemple :

39 // 100 donne 0, il reste 39 euros à rendre ;
39 // 50 donne 0, il reste 39 euros à rendre ;
39 // 20 donne 1, il reste 39 - 1 × 20 = 19 euros à rendre ;
19 // 10 donne 1, il reste 19 - 1 × 10 = 9 euros à rendre ;
9 // 5 donne 1, il reste 9 - 1 × 5 = 4 euros à rendre ;
4 // 2 donne 2, il reste 4 - 2 × 2 = 0 euro à rendre, terminé

donc 39 → [0, 2, 1, 1, 1, 0, 0].

Ecrivez un algorithme en pseudo-code, traduisez-le en Python et testez-le dans Thonny avec systeme_monetaire qui vaut [1, 2, 5, 10, 20, 50, 100] ou [1, 2, 6, 12, 24, 30, 60, 240] et quelques monnaies à rendre.

Si vraiment vous êtes coincé...

Voici une écriture de cet autre algorithme glouton pour le problème du rendu de la monnaie, avec les mêmes entrées et sorties :

📋 Texte

ind ← indice de la pièce de plus grande valeur dans `systeme_monetaire`  
restant ← somme  
tab_nb_pieces ← tableau de 7 zéros  
Tant que restant n'est pas nulle  
Faire  
    valeur_piece ← systeme_monetaire[ind]  
    tab_nb_pieces[ind] ← restant // valeur_piece  
    restant ← restant - tab_nb_pieces[ind] × valeur_piece  
    ind ← ind - 1  
Fin du Tant que