Problème du rendu de monnaie

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

C'est un problème qui se pose à chacun de nous quotidiennement, a fortiori aux distributeurs automatiques (le problème est alors compliqué par le fait que l'on ne dispose que d'un nombre limité de pièces de chaque type).

On rencontre des problèmes similaires dans l'utilisation des boites à poids.

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 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[modifier | modifier le code]

Définition[modifier | modifier le code]

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

S=(c_1,c_2,\ldots,c_n),

c_i représente la valeur de la ie pièce. On suppose que ces valeurs sont des entiers strictement croissants, et que c_1=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 T=(x_1,x_2,\ldots,x_n) qui minimise

\sum_{i=1}^n x_i

sous la contrainte

\sum_{i=1}^n x_i c_i = v.

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(v)

Exemple[modifier | modifier le code]

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 (x_1,x_2,x_3) qui minimise le nombre total x_1+x_2+x_3 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.

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 + 488 = 500×3 + 200×2 + 50×1 + 20×1 + 10×1 + 5×1 + 2×2, soit 3+2+1+1+1 = 8 billets et 1+2 = 3 pièces.

Un problème NP-difficile[modifier | modifier le code]

Difficulté[modifier | modifier le code]

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

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

Résolution par programmation dynamique[modifier | modifier le code]

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 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 à 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 :

M_S(v)=1+\min_{1\leq i\leq n} M_S(v-c_i).

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[modifier | modifier le code]

Définition[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

On ne connait 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.

Chang et Gill (1970)[modifier | modifier le code]

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 \nu telles que

 c_3\leq \nu<\frac{c_n(c_nc_{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 (1,7,23) est canonique, il suffit de tester les valeurs entre 23 et 234.

Kozen et Zaks (1994)[modifier | modifier le code]

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_3+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_n+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,

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_n\ln(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)[modifier | modifier le code]

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_1 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_1 fois la plus grosse pièce, m_2 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 m_k. C'est-à-dire que l'on prend i tel que m_i \ne 0, et \forall k \in [1, i-1], m_k =0 et j tel que m_j \ne 0, et \forall k \in [j+1, N], m_k = 0. 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_1 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 :

  • \forall k \in [1, j-1], m_k=g_k
  • m_j=g_j+1
  • \forall k \in [j+1, N], m_k=0

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

  • Le choix de i et j se fait en O(n^2)
  • Pour le test, il faut
    • Calculer c_{i-1}-1 (O(1))
    • Trouver les g_k correspondants à c_{i-1}-1 à l'aide de l'algorithme glouton (O(n))
    • Trouver les m_k correspondants grâce au théorème ci-dessus et aux valeurs des g_k (O(n))
    • Trouver w = \sum_{i=1}^{N}m_ic_i (O(n))
    • Trouver les g_k correspondants à w à l'aide de l'algorithme glouton (O(n))
    • Tester si \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 O(n^3)

Notes et références[modifier | modifier le code]

  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 G(v) en temps O(\ln(v) pour 1< v<c_n+c_{n-1} — soit un temps O(c_n\ln(c_n)) pour cette première étape, puis de vérifier G(v)>G(v-c_i)+1 en temps O(1) pour c_3+1<v<c_n+c_{n-1} — soit un temps 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[modifier | modifier le code]

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