problème des pièces de monnaie

En mathématiques, le problème des pièces de monnaie, également appelé le problème des pièces de Frobenius ou le problème de Frobenius d'après le mathématicien Georg Frobenius, est un problème diophantien linéaire. Il s'agit de 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. Par exemple, le plus grand montant que l'on ne peut pas exprimer avec des pièces de 3 et de 5 unités est 7 unités. La solution du problème pour un ensemble de pièces donné est appelée le nombre de Frobenius de cet ensemble. 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, on ne connaît pas de formule explicite ; toutefois, pour tout nombre fixé de valeurs faciales, il existe un algorithme qui calcule le nombre de Frobenius en temps polynomial (en fonction du logarithme des valeurs faciales données en entrée). On ne connaît pas d'algorithme polynomial comme fonction du nombre de valeurs faciales, et le problème général, où le nombre de valeurs faciales est arbitrairement grand, est NP-difficile.