Preuve de la NP-complétude du problème de
rendu de monnaie
Enoncé du problème
Le problème de rendu de monnaie consiste à rendre la somme M en utilisant un
nombre minimal de billets et pièces disponibles. Les billets et pièces disponibles
sont x1 , x2 , . . . , xr et l’objectif est de trouver des entiers k1 , k2 , . . . , kr ∈ N ∗ tels
que :
r
X
xi · ki = M
i=1
Pr
et la somme i=1 ki soit minimale.
Étape 1 : Le problème appartient à NP
Un problème appartient à la classe NP s’il existe un algorithme permettant de
vérifier une solution donnée en temps polynomial.
Dans le problème du rendu de monnaie, une solution candidate consiste à
donner les valeurs de k1 , k2 , . . . , kr , c’est-à-dire le nombre de billets ou pièces
utilisés pour chaque type de billet.
La vérification consiste à vérifier que la somme des valeurs rendues est égale
à M , c’est-à-dire vérifier si :
r
X
xi · ki = M
i=1
Cela peut être effectué en temps polynomial en calculant simplement la
somme. De plus, pourPvérifier que la solution est optimale, on peut également
r
vérifier que la somme i=1 ki est minimale en la comparant à d’autres solutions.
Cette vérification est également réalisable en temps polynomial.
Ainsi, le problème du rendu de monnaie appartient à NP.
1
Étape 2 : Réduction à un problème NP-complet
Pour montrer que le problème de rendu de monnaie est NP-complet, il nous
reste à prouver qu’il est au moins aussi difficile que certains problèmes NP-
complets déjà connus. Nous allons réduire un problème NP-complet bien connu,
le **problème du sac à dos** (Knapsack Problem), au problème du rendu de
monnaie.
Problème du sac à dos
Le problème du sac à dos consiste à choisir des objets parmi un ensemble d’objets
disponibles, chaque objet ayant une **valeur** et un **poids**, de sorte à
maximiser la valeur totale sans dépasser une capacité de poids donnée. Le but
est de trouver la combinaison d’objets qui respecte la contrainte de poids et
maximise la valeur totale.
Réduction du problème du sac à dos au problème de rendu
de monnaie
Nous pouvons interpréter le problème du rendu de monnaie comme un cas par-
ticulier du problème du sac à dos en considérant :
• Les poids des objets dans le problème du sac à dos deviennent les valeurs
des pièces et des billets x1 , x2 , . . . , xr dans le problème de rendu de mon-
naie.
• La valeur de chaque objet dans le problème du sac à dos devient le nombre
de billets utilisés.
• La capacité du sac dans le problème du sac à dos devient la somme M
que nous devons rendre avec les billets et pièces.
• L’objectif de maximiser la valeur dans le problème du sac à dos devient
l’objectif de minimiser le nombre total de billets dans le problème de rendu
de monnaie.
Ainsi, le problème de rendu de monnaie est une version du problème du sac à
dos où l’on cherche à minimiser le nombre total de billets utilisés pour atteindre
exactement la somme M .
Le problème du sac à dos est bien connu pour être NP-complet. Puisque
nous avons montré que le problème du rendu de monnaie peut être réduit au
problème du sac à dos, il en découle que le problème de rendu de monnaie est
également NP-complet.
Conclusion
Le problème de rendu de monnaie est NP-complet car :
2
• Il appartient à la classe NP, car la vérification d’une solution est réalisable
en temps polynomial.
• Il peut être réduit au problème du sac à dos, qui est NP-complet.
Cela prouve que le problème de rendu de monnaie est NP-complet.
