Problème du rendu de monnaie

Le problème du rendu de monnaie est un problème d'algorithmique. Il s'énonce de la façon suivante : é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 meilleure 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èces de un euro, par exemple). On rencontre des problèmes similaires dans l'utilisation des boites à poids.

Ce problème est NP-complet dans le cas général, c'est-à-dire difficile à résoudre. Cependant pour certains systèmes de monnaie dits canoniques, l'algorithme glouton est optimal, c'est-à-dire qu'il suffit de rendre systématiquement la pièce ou le billet de valeur maximale — ce tant qu'il reste quelque chose à rendre. 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.

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

${\displaystyle S=(c_{1},c_{2},\ldots ,c_{n}),}$

où ${\displaystyle c_{i}}$ représente la valeur de la i^e pièce. On suppose que ces valeurs sont des entiers strictement croissants, et que ${\displaystyle c_{1}=1}$ (sinon certaines sommes ne peuvent être rendues — voir le problème des pièces de monnaie).

É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 qui consiste à trouver un n-uplet d'entiers positifs ${\displaystyle T=(x_{1},x_{2},\ldots ,x_{n})}$ qui minimise

${\displaystyle \sum _{i=1}^{n}x_{i}}$

sous la contrainte

${\displaystyle \sum _{i=1}^{n}x_{i}c_{i}=v}$.

Ainsi, ${\displaystyle v}$ représente la somme de monnaie à rendre et ${\displaystyle x_{i}}$ le nombre de pièces ${\displaystyle 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 ${\displaystyle v}$.

On note ${\displaystyle M_{S}(v)}$ le nombre minimal de pièces d'un système ${\displaystyle S(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) :

(7,0,0), (5,1,0), (3,2,0), (1,3,0), (2,0,1), (0,1,1).

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

Pour rendre toute somme inférieure à 500 euros pièces il faut au plus 3 pièces pour les unités, 3 billets pour les dizaines et jusqu'à 2 billets pour les centaines, soit au plus 8 pièces ou billets. L'optimum au-delà est alors formé de (v div 500) billets de 500 euros, plus les pièces et billets nécessaires pour le reste (v mod 500) euros, soit au plus

(v div 500) + 8 pièces ou billets.

Ainsi, 1989 = 500×3 + 489 = 500×3 + 200×2 + 50×1 + 20×1 + 10×1 + 5×1 + 2×2, soit 3+2+1+1+1+1 = 9 billets et 2 pièces.

Complexité et algorithme pour le cas général

Complexité

Le problème du rendu de monnaie est NP-complet relativement au nombre |S| de valeurs disponibles.

On le montre par réduction à partir du problème du sac à dos^[1].

Résolution par programmation dynamique

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

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

${\displaystyle M_{S}(v)=1+\min _{1\leq i\leq n{\text{ et }}c_{i}\leq v}M_{S}(v-c_{i}).}$

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

Ci-contre, un exemple montrant le calcul de ${\displaystyle 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 ${\displaystyle 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 connaît pas de caractérisation des systèmes de pièces canoniques, mais il existe un algorithme efficace pour tester si un système donné est canonique.

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 ${\displaystyle \nu }$ telles que

${\displaystyle c_{3}\leq \nu <{\frac {c_{n}(c_{n}c_{n-1}+c_{n}-3c_{n-1})}{c_{n}-c_{n-1}}},}$

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 ${\displaystyle (1,7,23)}$ est canonique, il suffit de tester les valeurs entre 23 et 234.

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 ${\displaystyle v}$ telles que

${\displaystyle c_{3}+1<v<c_{n}+c_{n-1},}$

Par exemple, ceci réduit le test de canonicité du système ${\displaystyle (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 ${\displaystyle c_{3}+2}$ ou ${\displaystyle 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 ${\displaystyle v}$ pour laquelle l'algorithme glouton n'est pas optimal vérifie, pour au moins une pièce ${\displaystyle c_{i}}$ :

${\displaystyle G(v)>G(v-c_{i})+1,}$

où ${\displaystyle G(x)}$ est le nombre de pièces utilisées par l'algorithme glouton pour rendre ${\displaystyle x}$. L'intérêt est qu'il est bien plus rapide de vérifier l'inégalité ci-dessus (le calcul de ${\displaystyle G(x)}$ est linéaire en la taille ${\displaystyle \ln(x)}$ de ${\displaystyle 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 ${\displaystyle O(c_{n}\ln(c_{n}))}$, qui n'est cependant pas "efficace" au sens où il est exponentiel en la taille ${\displaystyle \ln(c_{n})}$ de la valeur ${\displaystyle c_{n}}$.

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 ${\displaystyle 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 ${\displaystyle c_{1}}$ représente la plus grosse pièce et ${\displaystyle c_{N}}$ la plus petite. Comme on veut que toutes les sommes soient possibles à réaliser, on prend ${\displaystyle c_{N}=1}$

L'algorithme optimal va utiliser, pour former pour la somme w, ${\displaystyle m_{1}}$ fois la plus grosse pièce, ${\displaystyle m_{2}}$ fois la deuxième plus grosse, ... et ${\displaystyle m_{N}}$ fois la plus petite.

Appelons ${\displaystyle i}$ et ${\displaystyle j}$ la première et la dernière entrée non nulle de la liste des ${\displaystyle m_{k}}$. C'est-à-dire que l'on prend i tel que ${\displaystyle m_{i}\neq 0}$, et ${\displaystyle \forall k\in [1,i-1],m_{k}=0}$ et j tel que ${\displaystyle m_{j}\neq 0}$, et ${\displaystyle \forall k\in [j+1,N],m_{k}=0}$. Notez que ${\displaystyle i}$ et ${\displaystyle j}$ peuvent être confondus (si la représentation minimale n'utilise qu'une seule pièce), et que ${\displaystyle i}$ est toujours strictement supérieur à 1 (la représentation minimale de w n'utilise jamais la plus grosse pièce).

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

Pearson prouve que :

• ${\displaystyle \forall k\in [1,j-1],m_{k}=g_{k}}$
• ${\displaystyle m_{j}=g_{j}+1}$
• ${\displaystyle \forall k\in [j+1,N],m_{k}=0}$

L'idée de l'algorithme est de prendre tout couple ${\displaystyle i}$, ${\displaystyle j}$ et de tester si on a bien un contre exemple.

• Le choix de ${\displaystyle i}$ et ${\displaystyle j}$ se fait en ${\displaystyle O(n^{2})}$
• Pour le test, il faut
  • Calculer ${\displaystyle c_{i-1}-1}$ (O(1))
  • Trouver les ${\displaystyle g_{k}}$ correspondants à ${\displaystyle c_{i-1}-1}$ à l'aide de l'algorithme glouton (O(n))
  • Trouver les ${\displaystyle m_{k}}$ correspondants grâce au théorème ci-dessus et aux valeurs des ${\displaystyle g_{k}}$ (O(n))
  • Trouver ${\displaystyle w=\sum _{i=1}^{N}m_{i}c_{i}}$ (O(n))
  • Trouver les ${\displaystyle g_{k}}$ correspondants à ${\displaystyle w}$ à l'aide de l'algorithme glouton (O(n))
  • Tester si ${\displaystyle \sum _{i=1}^{N}m_{k}<\sum _{i=1}^{N}g_{k}}$ (O(n)). Si c'est le cas, on a un contre exemple.

C'est donc bien du ${\displaystyle O(n^{3})}$

Notes et références

1. (en) G.S. Lueker, Two NP-complete problems in non negative integer programming, Report. 178, Computer Science Laboratory, Princeton University, 1975.
2. (en) S. K. Chang, A. Gill, Algorithmic Solution of the Change-Making Problem, Journal of the ACM 17 (1970), 113—122. (en ligne)
3. (en) D. Kozen, S. Zaks, Optimal Bounds for the Change-Making Problem, Theoretical Computer Science 123 (1994), 377—388. (en ligne)
4. Il suffit de calculer ${\displaystyle G(v)}$ en temps ${\displaystyle O(\ln(v)}$ pour ${\displaystyle 1<v<c_{n}+c_{n-1}}$ — soit un temps ${\displaystyle O(c_{n}\ln(c_{n}))}$ pour cette première étape, puis de vérifier ${\displaystyle G(v)>G(v-c_{i})+1}$ en temps ${\displaystyle O(1)}$ pour ${\displaystyle c_{3}+1<v<c_{n}+c_{n-1}}$ — soit un temps ${\displaystyle O(c_{n})}$ pour cette seconde étape.
5. (en) D. Pearson, A Polynomial-time Algorithm for the Change-Making Problem, Operations research letters 33 (2005), 231—234. (en ligne)

Bibliographie

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

• Portail de l'informatique théorique