5.3.1. Problema del cambio de monedas.
¿Cómo calcular cuántas monedas de cada tipo deben usarse, es decir la solución (x1, x2, ..., xn)?
Debemos analizar las decisiones que se tomaron en cada celda D[i, j]:
- Si el mínimo fue D[i-1, j], entonces no se utilizó ninguna moneda de tipo i.
- Si fue D[i, j - C[i]] + 1, entonces se utilizó una moneda de tipo i.
-
Algoritmo para obtener una solución:
1. Empezar con i= n, j=P y con una solución (x1=0, x2=0, ..., xn=0)
2. Si D[i, j] = D[i-1, j] entonces i:= i - 1
En otro caso, xi:= xi + 1; j:= j - C[i];
3. Si i=0 y j=0 entonces acabar. Sino volver al paso 2.
¿Cuál es el tiempo de ejecución del algoritmo para obtener la solución?
¿Es correcto el algoritmo? ¿Es aplicable el principio de optimalidad?