En mathématiques, le problème des pièces de monnaie est un problème qui consiste à déterminer le montant le plus élevé que l’on ne peut pas représenter en n’utilisant que des pièces de monnaie de valeurs faciales fixées.
Il existe une formule explicite pour le nombre de Frobenius dans le cas où il n’y a que deux valeurs de pièces.
Si le nombre de valeurs est plus grand que 2, on ne connaît pas de formule explicite et le problème devient NP-difficile.
Pour 2 pièces ayant pour valeurs a et b (premiers entre eux), la formule est la suivante :
(a – 1)(b – 1) – 1
Et le nombre de valeurs qu’on ne peut pas exprimer avec ces 2 pièces est :
(a – 1)(b – 1) // 2
Par exemple, avec des pièces de 2 et de 5 centimes, on ne peut pas exprimer le montant 3 centimes. ( car (2-1)(5-1)-1 = 3).
Et on ne peut pas exprimer seulement 2 valeurs (qui sont 1 et 3 centimes) avec des pièces de 2 et de 5 centimes.