Problème du rendu de monnaie

Énoncé du problème

Un commerçant cherche à rendre la monnaie à ses clients de façon optimale, c’est-à-dire avec le nombre minimal de pièces et de billets.

Dans ce problème,

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

Algorithme glouton

Un client nous achète un objet qui coûte 53 euros. Il paye avec un billet de 200 euros. Il faut donc lui rendre 147 euros, par exemple un billet de 100, deux billets de 20, un billet de 5 et une pièce de 2.

Afin de minimiser le nombre de pièces à rendre, on peut suivre 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 résout le problème étape par étape et un choix optimal est effectué à chacune de ces étapes (la pièce de plus grande valeur). Cet algorithme fait parti de la catégorie des algorithmes gloutons : chercher la solution optimale à partir d’optima locaux.

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

from typing import List
  1. Préparer le code suivant et étudier sa structure :
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

if __name__ == "__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(f"Je dois rendre : {a_rendre}")
    print(f"Je donne donc : {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.
    """
Réponse 
1
2
3
4
5
6

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.
    """
    return montant_client - prix
  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.
    """
Réponse 
 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
42
43
44

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.

    On reçoit : pieces = [1, 2, 5, 10, 20]
    On retourne : a_rendre = [x, z, y, a, b]
    """
    a_rendre = []

    for i in range(len(pieces) - 1, -1, -1):
        nbre = somme // pieces[i]
        somme = somme % pieces[i]
        a_rendre.append(nbre)

    return list(reversed(a_rendre))


def pieces_a_rendre_2(somme: int, pieces: List[int]):
    a_rendre = {}

    i = len(pieces) - 1
    while somme > 0:
        nbre = somme // pieces[i]
        somme = somme % pieces[i]
        a_rendre[pieces[i]] = nbre
        i = i - 1
    return a_rendre


def pieces_a_rendre_3(somme: int, pieces: List[int]) -> List[int]:
    a_rendre = [0] * len(pieces)

    i = len(pieces) - 1
    while somme > 0:
        nbre = somme // pieces[i]
        somme = somme % pieces[i]
        a_rendre[i] = nbre
        i = i - 1

    return list(reversed(a_rendre))
Code complet

Le code se trouve à : cette adresse

Algorithme de force brute

  1. On note $nb$ le nombre de pièces à rendre, prises dans la liste des pièces $p = [1, 2, 5, 10, 20, 50, 100, 200, 500]$, lorsque la somme à rendre est $x$.
    Écrire la relation de récurrence que doit vérifier $nb$.
Réponse

$$ nb(x) = \begin{cases} 0 & \text{ si } x = 0\cr 1 + nb(x - p[i]) & \text{ si } x - p[i] \geqslant 0 \cr \end{cases} $$

  1. En fait, on cherche le nombre minimal de pièces à rendre pour la somme $x$. Adapter la relation de récurrence.
Réponse

$$ nb(x) = \begin{cases} 0 & \text{ si } x = 0\cr 1 + \min{(nb(x - p[i]))} & \text{ si } x - p[i] \geqslant 0 \text{ et } i \in [0, \text{len}(p)[ \cr \end{cases} $$

  1. Écrire le schéma des appels récursifs pour $x=11$ et $p=[2,5,10]$.
Réponse
  1. Indiquer l’avantage et l’inconvénient de l’algorithme par Brute Force.
Réponse

Cet algorithme retourne une solution optimale mais calcule plusieurs fois les mêmes valeurs. Il est donc inutilisable si la valeur à retourner est importante.

  1. Réfléchir au code de la fonction dont la spécification est :
1
2
3
4
5
6
7

def nb_rendre(a_rendre: int, pieces: List[int]) -> int:
    """
    Détermine le nombre minimal de pièces
    à rendre.

    Algorithme récursif.
    """

Écrire le code de cette fonction.

Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def nb_rendre(a_rendre: int, pieces: List[int]) -> int:
    """
    Détermine le nombre minimal de pièces
    à rendre.

    Algorithme récursif.
    """
    if a_rendre == 0:
        return 0

    nb_min = float('inf')

    for i in range(len(pieces)):
        if pieces[i] <= a_rendre:
            nb = 1 + nb_rendre(a_rendre - pieces[i], pieces)
            if nb <= nb_min:
                nb_min = nb

    return nb_min
  1. Tester le code pour une somme à rendre de 13 puis de 130. Le résultat confirme-t-il la réponse à la question 4 ?
Code complet

Le code se trouve à : cette adresse

Compléments

  1. On souhaite maintenant écrire le code de la fonction pieces_a_rendre dont la spécification est :
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def pieces_a_rendre(somme: int,
                   pieces: Tuple[int],
                   serie: List[int],
                   series: List[Tuple[int]]) -> None:
    """
    Détermine toutes les combinaisons de pièces qui permettent de rendre la somme somme.
    pieces est le tuple des pièces disponibles.
    series est la liste des pièces à rendre.
    series est la liste des listes des pièces à rendre.
    """

Remarque

On peut bien sur créer une fonction enveloppe qui ne prendrait que la somme et la liste des pièces disponibles en argument et retournerait la liste des listes de pièces.

Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def pieces_a_rendre(somme: int,
                   pieces: Tuple[int],
                   serie: List[int],
                   series: List[Tuple[int]]) -> None:
    """
    Détermine toutes les combinaisons de pièces qui permettent de rendre la somme somme.
    """
    if somme == 0:
        series.append(serie)
        return None 

    for piece in pieces:
        if piece > somme:
            continue
        
        # Sauvegarde de la liste des pièces pour le retour arrière
        serie_sauv = list(serie)

        serie.append(piece) 
        pieces_a_rendre(somme - piece, pieces, serie, series)
        
        serie = serie_sauv

  1. Tester le code pour une somme à rendre de 13 puis de 130. Obtient-on rapidement un résultat pour cette dernière valeur ?

  2. Comment déterminer le nombre minimum de pièces à retourner ?

Réponse

Le nombre minimum de pièces est égal à la plus petite longueur des listes éléments de la liste series.

Programmation dynamique (mémoïsation)

  1. Rappeler quel est l’objectif de la programmation dynamique.
Réponse

La programmation dynamique, comme la méthode diviser-pour-régner, résout des problèmes en combinant des solutions de sous-problèmes.

  • Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent récursivement, puis combinent leurs solutions pour résoudre le problème initial.
  • La programmation dynamique, quant à elle, peut s’appliquer même lorsque les sous-problèmes ne sont pas indépendants, c’est-à-dire lorsque des sous-problèmes ont des sous-sous-problèmes communs. Dans ce cas, un algorithme diviser-pour-régner fait plus de travail que nécessaire, en résolvant plusieurs fois le sous-sous-problème commun. Un algorithme de programmation dynamique résout chaque sous-sous-problème une seule fois et mémorise sa réponse dans un tableau, évitant ainsi le recalcul de la solution chaque fois que le sous-sous-problème est rencontré.

La programmation dynamique est, en général, appliquée aux problèmes d’optimisation. Dans ce type de problèmes, il peut y avoir de nombreuses solutions possibles. Chaque solution a une valeur, et on souhaite trouver une solution ayant la valeur optimale (minimale ou maximale). Une telle solution est une solution optimale au problème, et non pas la solution optimale, puisqu’il peut y avoir plusieurs solutions qui donnent la valeur optimale.

  1. Le manque d’efficacité de la méthode force brute a pour origine les multiples calculs redondants. Mettre en œuvre la méthode de mémoïsation afin d’améliorer l’efficacité du code de la fonction nb_rendre.
Réponse 
 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

def nb_rendre(a_rendre: int, pieces: List[int]) -> int:
    """
    Détermine le nombre minimal de pièces
    à rendre.

    Algorithme récursif avec mémoïsation.
    """
    dic_a_rendre = {0: 0}

    def _nb_rendre(a_rendre: int, pieces: List[int], dic: Dict[int, int]) -> int:
        """
        Version mémoïsée de la fonction nb_rendre.
        """
        if a_rendre not in dic.keys():
            nb_min = float('inf')
        
            for i in range(len(pieces)):
                if pieces[i] <= a_rendre:
                    nb = 1 + _nb_rendre(a_rendre - pieces[i], pieces, dic)
                    if nb <= nb_min:
                        nb_min = nb
            
            dic[a_rendre] = nb_min

        return dic[a_rendre]

    return _nb_rendre(a_rendre, pieces, dic_a_rendre)
Code complet

Le code se trouve à : cette adresse

Programmation dynamique (méthode tabulaire)

  1. Rappeler quel est l’objectif de la programmation dynamique.
Réponse

La programmation dynamique, comme la méthode diviser-pour-régner, résout des problèmes en combinant des solutions de sous-problèmes.

  • Les algorithmes diviser-pour-régner partitionnent le problème en sous-problèmes indépendants qu’ils résolvent récursivement, puis combinent leurs solutions pour résoudre le problème initial.
  • La programmation dynamique, quant à elle, peut s’appliquer même lorsque les sous-problèmes ne sont pas indépendants, c’est-à-dire lorsque des sous-problèmes ont des sous-sous-problèmes communs. Dans ce cas, un algorithme diviser-pour-régner fait plus de travail que nécessaire, en résolvant plusieurs fois le sous-sous-problème commun. Un algorithme de programmation dynamique résout chaque sous-sous-problème une seule fois et mémorise sa réponse dans un tableau, évitant ainsi le recalcul de la solution chaque fois que le sous-sous-problème est rencontré.

La programmation dynamique est, en général, appliquée aux problèmes d’optimisation. Dans ce type de problèmes, il peut y avoir de nombreuses solutions possibles. Chaque solution a une valeur, et on souhaite trouver une solution ayant la valeur optimale (minimale ou maximale). Une telle solution est une solution optimale au problème, et non pas la solution optimale, puisqu’il peut y avoir plusieurs solutions qui donnent la valeur optimale.

  1. Le manque d’efficacité de la méthode force brute a pour origine les multiples calculs redondants. Mettre en œuvre la méthode de ascendante afin d’améliorer l’efficacité du code de la fonction nb_rendre.
Réponse 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def nb_rendre(a_rendre: int, pieces: List[int]) -> int:
    """
    Détermine le nombre minimal de pièces
    à rendre.

    Algorithme itératif, méthode ascendante.
    """
    nbres = [float('inf')] * (a_rendre + 1)  # Tableau des valeurs
    nbres[0] = 0

    for somme in range(1, len(nbres)):
        for piece in pieces:
            if (somme - piece) >= 0:
                nbres[somme] = min(nbres[sommes], 1 + nbres[somme - piece])

    return nbres[a_rendre]

En résumé

Rendu de monnaie - Nombre de pièces à rendre - Toutes les méthodes 
  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
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

"""
Les mille et unes façon de rendre la monnaie.
"""
from typing import List, Dict


def glouton(somme: int, pieces: List[int]) -> int:
    """
    Retourne le nombre de pièces nécessaires pour 
    rendre la monnaie pour somme.

    Méthode gloutonne, pièces est censé être trié
    dans le sens décroissant.
    """
    nbre = 0  # nombre de pièces à rendre

    for piece in pieces:
        nbre += somme // piece
        somme = somme % piece

    return nbre


def force_brute(somme: int, pieces: List[int]) -> int:
    """
    Retourne le nombre de pièces nécessaires pour 
    rendre la monnaie pour somme.

    Méthode force brute.
    """
    if somme == 0:
        return 0

    nbre_min = float('inf')
    for piece in pieces:
        if somme - piece >= 0:
            nbre_new = 1 + force_brute(somme - piece, pieces)
            if nbre_new < nbre_min:
                nbre_min = nbre_new

    return nbre_min


def memoisation(somme: int,
                pieces: List[int],
                memo: Dict[int, int] = {0: 0}) -> int:
    """
    Retourne le nombre de pièces nécessaires pour 
    rendre la monnaie pour somme.

    Programmation dynamique : mémoïsation.
    """
    if somme not in memo:
        nbre_min = float('inf')
        for piece in pieces:
            if somme - piece >= 0:
                nbre_new = 1 + memoisation(somme - piece, pieces, memo)
                if nbre_new < nbre_min:
                    nbre_min = nbre_new
        memo[somme] = nbre_min

    return memo[somme]


def tabulaire(somme: int, pieces: List[int]) -> int:
    """
    Retourne le nombre de pièces nécessaires pour 
    rendre la monnaie pour somme.

    Programmation dynamique : méthode tabulaire.
    Fonction enveloppe.
    """
    nbre_pour_somme = [float('inf') for i in range(somme + 1)]
    nbre_pour_somme[0] = 0

    def _tabulaire(somme: int, pieces: List[int], nbre_pour_somme):
        """
        Mise en œuvre de la méthode tabulaire.
        """
        for somme_a_rendre in range(1, somme + 1):
            for piece in pieces:
                if somme_a_rendre - piece >= 0:
                    nbre = 1 + nbre_pour_somme[somme_a_rendre - piece]

                    if nbre < nbre_pour_somme[somme_a_rendre]:
                        nbre_pour_somme[somme_a_rendre] = nbre

        return nbre_pour_somme[somme]

    return _tabulaire(somme, pieces, nbre_pour_somme)


if __name__ == "__main__":
    somme_a_rendre = 60
    pieces = [25, 20, 1]

    nbres_pieces = glouton(somme_a_rendre, pieces)
    print(
        f"Méthode gloutonne pour rendre {somme_a_rendre} : {nbres_pieces} pieces."
    )

    nbres_pieces = force_brute(somme_a_rendre, pieces)
    print(
        f"Méthode force-brute pour rendre {somme_a_rendre} : {nbres_pieces} pieces."
    )

    nbres_pieces = memoisation(somme_a_rendre, pieces)
    print(
        f"Méthode mémoïsation pour rendre {somme_a_rendre} : {nbres_pieces} pieces."
    )

    nbres_pieces = tabulaire(somme_a_rendre, pieces)
    print(
        f"Méthode tabulaire pour rendre {somme_a_rendre} : {nbres_pieces} pieces."
    )
Programmation dynamique 

Voir également