4.1. Método general.
Candidatos iniciales: todos los tipos de monedas disponibles. Supondremos una cantidad ilimitada de cada una.
Solución: conjunto de monedas que suman la cantidad P.
Una solución será de la forma (x1, x2, x3, x4, x5, x6, x7, x8), donde xi es el número de monedas de tipo i. Suponemos que la moneda i vale ci.
Funciones:
- solución. El valor actual será solución si ? xi·ci = P
- objetivo. La función a minimizar es ? xi, el número de monedas resultante.
- seleccionar. Elegir en cada paso la moneda de valor más alto posible, pero menor que el valor que queda por devolver.
- factible. Valdrá siempre verdad.
En lugar de seleccionar monedas de una en una, podemos usar la división entera y coger todas las monedas posibles de mayor valor.