CHAPITRE 2 : RENDRE LA MONNAIE

Reprenons le comptoir de Mama Ngono. Son problème est un classique de l'algorithmique, et il a l'avantage d'être l'un des rares où le glouton a toujours raison : du moins avec notre monnaie.

Le problème, posé proprement

On dispose d'un ensemble de coupures. En zone franc CFA d'Afrique centrale :

pieces  : 1, 2, 5, 10, 25, 50, 100, 500
billets : 500, 1000, 2000, 5000, 10000

On doit rendre un montant donné. L'objectif est de rendre le moins de coupures possible.

Pourquoi le moins ? D'abord pour la cliente, qui ne veut pas repartir avec quarante pièces. Ensuite et surtout pour Mama Ngono : si elle vide sa caisse de petite monnaie dès le matin, elle ne pourra plus rendre à personne l'après-midi.

La stratégie gloutonne

À chaque étape, donner la plus grosse coupure qui ne dépasse pas ce qui reste à rendre.

Le code

COUPURES = [1, 2, 5, 10, 25, 50, 100, 500, 1000, 2000, 5000, 10000]


def rendre(montant, coupures=COUPURES):
    # Rend la liste des coupures a donner, des plus grosses aux plus petites
    reste = montant
    rendu = []

    for piece in sorted(coupures, reverse=True):   # de la plus grosse
        while reste >= piece:                      # tant qu'elle tient
            rendu.append(piece)
            reste -= piece

    return rendu if reste == 0 else None           # None : rendu impossible

Essayons :

>>> rendre(1850)
[1000, 500, 100, 100, 100, 50]          # 6 coupures

>>> rendre(7675)
[5000, 2000, 500, 100, 50, 25]          # 6 coupures

>>> rendre(940)
[500, 100, 100, 100, 100, 25, 10, 5]    # 8 coupures

Une version plus parlante

La liste brute n'est pas très lisible pour un humain. Regroupons :

from collections import Counter


def annoncer(montant):
    rendu = rendre(montant)
    if rendu is None:
        print("impossible de rendre", montant)
        return

    compte = Counter(rendu)
    for valeur in sorted(compte, reverse=True):
        nombre = compte[valeur]
        support = "billet" if valeur >= 500 else "piece"
        if nombre > 1:
            support += "s"
        print("%d %s de %d FCFA" % (nombre, support, valeur))
    print("et le compte est bon.")

>>> annoncer(1850)
1 billet de 1000 FCFA
1 billet de 500 FCFA
3 pieces de 100 FCFA
1 piece de 50 FCFA
et le compte est bon.

Est-ce vraiment le minimum ?

Six coupures pour 1 850 FCFA. Existe-t-il une combinaison à cinq ? À quatre ?

On peut le vérifier par force brute, en cherchant le minimum absolu pour chaque montant. Nous l'avons fait pour tous les montants de 1 à 3 000 FCFA : le glouton donne le minimum à chaque fois, sans exception.

Le système où le glouton se trompe

Imaginons maintenant une monnaie fantaisiste qui n'aurait que trois coupures : 1, 3 et 4. Et rendons 6.

Le glouton a pris le 4 parce qu'il était le plus gros. Ce faisant, il s'est condamné à finir avec deux pièces de 1. En renonçant au 4, on fait mieux.

Le glouton n'échoue pas par bêtise : il échoue parce qu'il ne sait pas que renoncer au meilleur choix immédiat peut ouvrir une meilleure suite.

Noter que sur ce même système, rendre 8 fonctionne très bien : le glouton donne 4 + 4, ce qui est optimal. L'échec n'est pas systématique, il dépend du montant. C'est ce qui le rend difficile à repérer.

Quand on ne peut pas rendre du tout

Dernier cas à traiter : avec un système sans pièce de 1, certains montants sont tout bonnement impossibles.

>>> rendre(7, [2, 5])        # on ne peut pas faire 7 avec des 2 et des 5
None

Le glouton prendrait 5, puis resterait bloqué sur 2, alors que 7 est réellement impossible ici. Mais attention : dans d'autres cas, le glouton échoue alors qu'une solution existe. Avec le système {3, 4} et un montant de 6, il prend 4, reste 2, bloqué, alors que 3 + 3 marchait parfaitement.

C'est pourquoi notre fonction renvoie None plutôt que de prétendre que c'est impossible : elle n'en sait rien.

Complexité

Si l'on note c le nombre de coupures différentes et n le nombre total de pièces rendues :

Autrement dit : immédiat. C'est pour cela que Mama Ngono n'a pas besoin d'y réfléchir.

reste 8 : on prend 5   ->  reste 3
reste 3 : on prend 1   ->  reste 2
reste 2 : on prend 1   ->  reste 1
reste 1 : on prend 1   ->  reste 0

resultat : 5 + 1 + 1 + 1 = 4 coupures

def minimum_vrai(montant, coupures):
    INFINI = float("inf")
    table = [0] + [INFINI] * montant      # table[m] = minimum pour m

    for m in range(1, montant + 1):
        for piece in coupures:
            if piece <= m and table[m - piece] + 1 < table[m]:
                table[m] = table[m - piece] + 1

    return table[montant]


def est_canonique(coupures, jusqua=3000):
    for m in range(1, jusqua + 1):
        glouton = rendre(m, coupures)
        if glouton is None or len(glouton) != minimum_vrai(m, coupures):
            return False, m          # le premier montant qui coince
    return True, None

>>> est_canonique([1, 2, 5, 10, 25, 50, 100, 500, 1000])
(True, None)

>>> est_canonique([1, 3, 4])
(False, 6)

def rendre_avec_stock(montant, caisse):
    # caisse : dictionnaire {valeur: quantite disponible}
    reste = montant
    rendu = []

    for piece in sorted(caisse, reverse=True):
        disponible = caisse[piece]
        # on en prend le moins possible entre ce qu'on a et ce qui tient
        nombre = min(disponible, reste // piece)
        rendu.extend([piece] * nombre)
        reste -= piece * nombre

    return rendu if reste == 0 else None

>>> caisse = {1000: 2, 500: 1, 100: 10, 50: 4, 25: 4}
>>> rendre_avec_stock(1850, caisse)
[1000, 500, 100, 100, 100, 50]