Dado un monto M de monedas y un conjunto de denominaciones D (billetes o monedas) se busca la mínima cantidad de denominaciones cuya suma sea M.
No existen restricciones sobre el número de billetes o monedas de una denominación y sobre el uso repetido de billetes o monedas.
Vamos aplicar un algoritmo voraz: se elige la opción óptima en cada paso con la esperanza de llegar a una solución general óptima.
Sea un monto de M=36 monedas y denominaciones D={1,2,5,10,20}. Se elige en cada paso la mayor moneda posible y así sucesivamente:
- paso 1: 36-20=16
- paso 2: 16-10=6
- paso 3: 6-5=1
- paso 4: 1-1=0
Por tanto la solución general es: S={20,10,5,1} que suman 36. Además es óptima porque no existen otra solución con menos monedas.
No siempre la suma de las soluciones óptimas de cada paso dan una solución óptima general.
Si ahora las denominaciones son D={1,2,5,10,18,20} también se tiene:
- paso 1: 36-20=16
- paso 2: 16-10=6
- paso 3: 6-5=1
- paso 4: 1-1=0
- paso 1: 39-20=19
- paso 2: 19-18=1
- paso 3: 1-1=0
Para que el algoritmo no falle nunca es necesario que cada clase de moneda sea igual o mayor que una sucesión de potencias. No puede haber dos clases de monedas que cumplan la misma condición.
$$k^0,k^1,k^2,\cdots k^n$$
En nuestro ejemplo válido:
$$2^0\leq1, 2^1\leq2,2^2\leq5,2^3\leq10,2^4\leq20$$
En las monedas del euro se cumple este criterio:
$$2^0\leq1, 2^1\leq2,2^2\leq5,2^3\leq10,2^4\leq20,2^5\leq50,2^6\leq100$$
Para que no falle nunca se utiliza la Programación Dinámica.