Problème du rendu de monnaie

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)}$.

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.

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].

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}$.

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.

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.

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})}$