4.1. Método general.
Ejemplo Sencillo. Problema del cambio de monedas.
Disponemos de monedas de euro con valores de 1, 2, 5, 10, 20 y 50 céntimos de euro (c€), 1 y 2 euros (€).
Construir un algoritmo que dada una cantidad P devuelva esa cantidad con monedas de estos tipos, usando un número mínimo de monedas.
P. ej.: para devolver 3.89 €: 1 monedas de 2€, 1 moneda de 1€, 1 moneda de 50 c€, 1 moneda de 20 c€, 1 moneda de 10 c€ , 1 moneda de 5 c€ y 2 monedas de 2 c€. Total: 8 monedas.
Podemos aplicar la técnica voraz: en cada paso añadir una moneda nueva a la solución actual, hasta que el valor llegue a P.