Problème du rendu de monnaie

Le problème du rendu de monnaie est le suivant : étant donné un système de monnaie (pièces et billets), comment rendre une somme donnée de façon optimale, c'est-à-dire avec le nombre minimal de pièces et billets ? Par exemple, la meilleur façon de rendre 7 euros est de rendre un billet de cinq et une pièce de deux, même si d'autres façons existent (rendre 7 pièce de un euro, par exemple). C'est un problème qui se pose à chacun de nous quotidiennement, a fortiori aux distributeurs automatiques (bien qu'en réalité, le problème soit compliqué par le fait qu'on ne dispose que d'un certain nombre de pièces de chaque type).

Ce problème s'avère en général difficile (NP-difficile, pour être précis), mais il existe cependant des systèmes particuliers — dits canoniques — dans lesquels il est simple : il suffit de rendre systématiquement la pièce ou le billet de valeur maximale — ce tant que qu'il reste quelque chose à rendre et, bien sûr, sans jamais rendre plus que nécessaire (on parle d'algorithme glouton). C'est la méthode employée en pratique, ce qui se justifie car la quasi-totalité des systèmes ayant cours dans le monde sont canoniques.

Il n'existe pas, à ce jour, de caractérisation générale des systèmes canoniques, mais il existe une méthode efficace pour déterminer si un système donné est canonique (un algorithme polynomial en le nombre de pièces et billets du système).

Formalisation

Définition

Les billets et pièces jouant ici le même rôle, on suppose pour simplifier qu'il n'y a que des pièces. Un système de pièces est alors un n-uplet

où c_i représente la valeur de la i^e pièce. On suppose que ces valeurs sont des entiers strictement croissants, et que c₁ = 1 (sinon certaines sommes ne peuvent être rendues — voir en:coin problem).

Étant donné un système S et un entier positif v, le problème de rendu de monnaie est le problème d'optimisation combinatoire (S,v) qui consiste à trouver un n-uplet d'entiers positifs qui minimise

sous la contrainte

Ainsi, v représente la somme de monnaie à rendre et x_i le nombre de pièces c_i à utiliser. La quantité à minimiser est donc le nombre total de pièces rendues, la condition à vérifier traduisant simplement le fait qu'il faut bien rendre la somme v.

On note M_S(v) le nombre minimal de pièces d'un système S pour rendre la valeur v

Exemple

Dans la zone euro, le système en vigueur est, en mettant de côté les centimes d'euros :

S = (1,2,5,10,20,50,100,200,500).

Il y a par exemple six triplets de pièces (ou billets) de 1, 2 et 5 euros qui permettent de rendre 7 euros (les billets de 10 euros ou plus étant inutiles) :

La solution au problème de rendu de monnaie (S,7) est alors le triplet (x₁,x₂,x₃) qui minimise le nombre total x₁ + x₂ + x₃ de pièces rendues, soit (0,1,1), c'est-à-dire une pièce de 2 euros et une de 5 (un billet). On a donc M_(1,2,5)(7) = 2.

Un problème NP-difficile

Réduction au problème du sac à dos

On montre que le problème du rendu de monnaie est NP-difficile par Réduction au problème du sac à dos^[1].

Résolution par programmation dynamique

Exemple : calcul de M_(1,7,23)(28) par programmation dynamique, visualisé sous forme d'arbre.

Un moyen conceptuellement simple de trouver le nombre M_S(v) de pièces permettant de rendre la valeur v dans le système de pièces , est la programmation dynamique. En effet, supposons qu'on sache rendre de façon optimale toutes les valeurs strictement inférieure à v. Pour rendre v, il faut au moins une pièce, à prendre parmi n possibles. Une fois choisie cette pièce, la somme restante est inférieure strictement à v, donc on sait la rendre de façon optimale. Il suffit donc d'essayer les n possibilités :

Le nombre de calculs à effectuer est proportionnel à v, donc exponentiel en la taille de v (sauf si v est codé en unaire…).

Ci-contre, un exemple montrant le calcul de M_(1,7,23)(28) par programmation dynamique. Un arbre est construit. Sa racine est la somme à rendre. Un nœud représente une somme intermédiaire. Les fils d'un nœud correspondent aux sommes restant à rendre selon la dernière pièce rendue (1, 7, ou 23, chaque pièce correspondant à une couleur d'arête attitrée). La construction de l'arbre se fait en largeur d'abord, c'est-à-dire qu'on calcule les fils de tous les nœuds d'un niveau avant de passer au niveau suivant, et on s'arrête dès qu'un nœud 0 est trouvé : le chemin allant de la racine à ce nœud permet de rendre la monnaie avec un minimum de pièces. Ici, on atteint 0 en rendant quatre pièces de 7 (chemin vert de longueur quatre), donc M_(1,7,23)(28) = 4.

Systèmes canoniques

Définition

La méthode "usuelle" pour rendre la monnaie est celle de l'algorithme glouton : tant qu'il reste quelque chose à rendre, choisir la plus grosse pièce qu'on peut rendre (sans rendre trop). C'est un algorithme très simple et rapide, et on appelle canonique un système de pièces pour lequel cet algorithme donne une solution optimale quelle que soit la valeur à rendre.

Exemples

Il se trouve que presque tous les systèmes de pièces réels de par le monde sont canoniques (dont celui de l'euro), ce qui justifie a posteriori la méthode "usuelle" de rendu de monnaie. Mais un contre-exemple historique est le système anglais avant sa réforme en 1971. En fait, un système pris au hasard n'a pas de raison d'être canonique. Par exemple le système (1,3,4), pour lequel l'algorithme glouton calcule 6 = 4 + 1 + 1 alors qu'on peut rendre une pièce en moins en remarquant que 6 = 3 + 3.

Caractérisation

On ne connait pas de caractérisation des systèmes de pièce canoniques, mais il existe un algorithme efficace pour tester si un système donné est canonique.

Chang et Gill (1970)

Le premier pas a été fait en 1970 par Chang et Gill, qui montrent qu'il existe certaines valeurs, en nombre fini, telles que si l'algorithme glouton est optimal pour toutes ces valeurs, alors il est optimal pour n'importe quelle valeur (et donc le système est canonique)^[2]. Plus précisément, ils montrent qu'il suffit de tester les valeurs ν telles que

c'est-à-dire, pour chacune de ces valeurs, de calculer une solution optimale et de la comparer à celle donnée par l'algorithme glouton. Par exemple, pour déterminer si le système (1,7,23) est canonique, il suffit de tester les valeurs entre 23 et 234.

Kozen et Zaks (1994)

En 1994, Kozen et Zaks améliorent le résultat précédent sur deux points^[3]. D'une part, ils montrent qu'il suffit en fait de tester les valeurs v telles que

c₃ + 1 < v < c_n + c_{n − 1},

Par exemple, ceci réduit le test de canonicité du système (1,7,23) aux valeurs entre 25 et 29 (soit 5 valeurs au lieu de 212 — il devient facile de trouver à la main une valeur montrant que ce système n'est pas canonique). Ils montrent aussi que ces bornes sont optimales, c'est-à-dire qu'il existe des systèmes nécessitant de tester les valeurs c₃ + 2 ou c_n + c_{n − 1} − 1.

D'autre part, ils montrent que si un système n'est pas canonique, alors la plus petite valeur v pour laquelle l'algorithme glouton n'est pas optimal vérifie, pour au moins une pièce c_i :

G(v) > G(v − c_i) + 1,

où G(x) est le nombre de pièces utilisées par l'algorithme glouton pour rendre x. L'intérêt est qu'il est bien plus rapide de vérifier l'inégalité ci-dessus (le calcul de G(x) est linéaire en la taille ln(x) de x) que de calculer, comme le fait l'algorithme de Chang et Gill, une solution optimale et de la comparer à celle donnée par l'algorithme glouton (le calcul d'une solution optimal est NP-difficile, comme vu plus haut).

Ceci donne^[4] un algorithme en O(c_nln(c_n)), qui n'est cependant pas "efficace" au sens où il est exponentiel en la taille ln(c_n) de la valeur c_n.

Pearson (1994)

Le résultat précédent est peu après amélioré par Pearson^[5]. Ce dernier donne un algorithme polynomial (plus précisément, cubique) en le nombre de pièces du système, donc jugé "efficace".

Théorème

Si un système de N pièces n'est pas canonique, alors il existe une somme w telle que:

• l'algorithme glouton n'est pas optimal pour w
• l'algorithme glouton est optimal pour toutes les sommes inférieures à w

Note: les pièces seront ici classées de la plus grosse à la plus petite. C'est-à-dire que c₁ représente la plus grosse pièce et c_N la plus petite. Comme on veut que toutes les sommes soient possibles à réaliser, on prend c_N = 1

L'algorithme optimal va utiliser, pour former pour la somme w, m₁ fois la plus grosse pièce, m₂ fois la deuxième plus grosse, ... et m_N fois la plus petite.

Appelons i et j la première et la dernière entrée non nulle de la liste des v_k. C'est-à-dire que l'on prend i tel que , et et j tel que , et . Notez que i et j peuvent être confondus (si la représentation minimale n'utilise qu'une seule pièce), et que i est toujours strictement supérieur à 1 (la représentation minimale de w n'utilise jamais la plus grosse pièce).

Appelons désormais g_k les indices de la représentation gloutonne de c_{i − 1} − 1. C'est-à-dire que g₁ est le nombre de fois que l'algorithme glouton va utiliser la plus grosse pièce pour former la somme c_{i − 1} − 1, etc.

Pearson prouve que :

• 
• m_j = g_j + 1
• 

On peut donc, pour un i et un j fixé, calculer tous les coefficients m_k en un temps O(n). Ainsi, en testant toutes les valeurs possibles de i et j, on peut créer un algorithme déterminant si un système est canonique en un temps O(n³).

Notes et références

Bibliographie

• (en) J. Shallit, What This Country Needs is an 18c Piece, The Mathematical Intelligencer 25 (2003), 20—25. (en ligne)

• Portail des mathématiques