C16.5 : Rendu de monnaie

Le problème du rendu de monnaie

Étant donné un système monétaire (c'est-à-dire un ensemble de pièces et billets), comment rendre une somme donnée avec le nombre minimal de pièces et billets ?

Pièces et billets du système monétaire européen

Solution au problème par un algorithme glouton

Principe de la solution avec l'algorithme glouton

Pour résoudre ce problème avec l'algorithme glouton, on choisit, tant que c'est possible, la pièce/billet de plus grande valeur.

Système monétaire canonique

A priori, l'algorithme glouton ne donne pas la meilleure solution.

Cependant, on peut montrer que, pour certains systèmes de pièces, l'algorithme glouton donne bien la meilleure solutions. Ces systèmes monétaires sont qualifiés de "systèmes monétaires canoniques". C'est le cas de tous les systèmes monétaires actuels.

Solution au problème par un algorithme récursif

Présentation

Nous allons voir dans cette partie un programme récursif qui teste toutes les combinaisons possibles. Ainsi, s'il y a une solution, le programme conduira nécessairement à la solution optimale.

Relation de récurrence

Notons \(p_1\), \(p_2\), ..., \(p_i\), ..., \(p_n\) les pièces disponibles.

Considérons une somme \(S\) et notons \(nb(S)\) le plus petit nombre de pièces possible pour rendre cette somme.

L'ensemble des sommes que l'on peut rendre avec une pièce de plus (c'est-à-dire avec \(nb(S)+1\) pièces) est : \(S-p_1\), \(S-p_2\), ..., \(S-p_i\), ..., \(S-p_n\). Avec \(p_i\) inférieur ou égal à \(S\).

On peut alors calculer le plus petit nombre de pièces nécessaire pour chacune de ces sommes, c'est-à-dire : \(nb(S-p_1)\), ..., \(nb(S-p_i)\), ..., \(nb(S-p_n)\). Avec \(p_i\) inférieur ou égal à S.

De cet ensemble de valeur, il ne faut garder que la plus petite.

Autrement dit, \(nb(S) = 1 + min_{\text{Pour tous les } i \text{ tels que } p_i < S \text{ }}(nb(S-p_i))\)

La récurrence peut s'exprimer de la façon suivante :

  • - si \(S = 0\) : \(nb(S)=0\)
  • - si \(S > 0\) : \(nb(S)=1+min_{\text{sur }i\text{ }}(nb(S-p_i))\)

Code python

1) Compléter la fonction récursive ci-dessous.

def rendu_rec(liste_pieces, somme):
    """
    Renvoie le nombre minimal de pièces pour rendre une somme donnée.
    Paramètres :
        liste_pieces (list) : Liste des montants des pièces disponibles.
                              La valeur 1 doit toujours être dans la  liste.
        somme (int) : Montant à rendre.
    Return :
        (int)
    """
    if somme == 0:
        return ________
    nb_pieces = ________   # au pire, il faut autant de pièces de 1 que la somme à rendre
    for piece in liste_pieces:
        if piece <= ________:
            nb_pieces_tmp = 1 + rendu_rec(liste_pieces, somme - piece)
            if _______________ :
                _______________
    return nb_pieces

2) Détailler le déroulement de l'algorithme pour l'instruction suivante : rendu_rec([1,3,5], 9)

3) L'algorithme vous semble-t-il efficace ? Comment l'améliorer ?

Solution au problème par programmation dynamique (version ascendante)

Afin de mémoriser les calculs intermédiaires, on utilisera une liste (un tableau) où les positions correspondent aux sommes possibles. La liste contiendra donc s + 1 cases.

La liste sera initialisée avec des 0 qui seront progressivement remplacés par le plus petit nombre de pièce nécessaire pour rendre la somme correspondant à la position.

1*) Proposer une fonction (non récursive) rendu_dyn_asc(liste_pieces, somme) qui renvoie le plus petit nombre de pièces nécessaire pour rendre la somme.

2*) Proposer une variante de cette fonction qui renvoie la liste des pièces correspondant au meilleur rendu de monnaie. On pourra utiliser au choix une liste , une liste de listes ou un dictionnaire.