Problema de la moneda

El problema de la moneda (también conocido como el problema de la moneda de Frobenius o el problema de Frobenius, en honor al matemático Ferdinand Frobenius) es un problema matemático que consiste en averiguar cuál es la mayor cantidad de dinero que no puede obtenerse, utilizando solo monedas de denominaciones específicas. Por ejemplo, la cantidad más grande de dinero que no se puede obtener usando solo monedas de 3 y de 5 unidades es 7 unidades. La solución a este problema para un conjunto dado de denominaciones de moneda se le denomina el número Frobenius de dicho conjunto. El número de Frobenius existe siempre que el máximo común divisor del conjunto de las denominaciones de moneda no sea mayor que 1. Hay una fórmula explícita para el número Frobenius cuando sólo hay monedas de dos denominaciones diferentes, x y y : xy − x − y. Si el número de denominaciones de moneda es tres o más, no se conoce ninguna fórmula explícita; pero, para cualquier número fijo de denominaciones de monedas, hay un algoritmo que calcula el número de Frobenius en tiempo polinomial (en los logaritmos de las denominaciones de monedas que forman la entrada). No se conoce ningún algoritmo de tiempo polinomial en el número de denominaciones de monedas, y es NP-Hard el problema general en el cual el número de denominaciones de monedas puede ser tan grande como se desee.