Diapositiva PPT
Definición de la ecuación recurrente:
Cambio (i, Q), el problema de calcular el número mínimo de monedas necesario para devolver una cantidad Q, usando los i primeros tipos de monedas (es decir los tipos 1...i).
La solución de Cambio(i, Q) puede que utilice al menos una moneda de tipo i o puede que no utilice ninguna.
- Si no usa ninguna moneda de ese tipo: Cambio(i, Q) = Cambio(i - 1, Q)
- Si usa una moneda (al menos) de tipo i: Cambio(i, Q) = Cambio(i, Q - ci) + 1
En cualquier caso, el valor será el mínimo entre ambas opciones:
Cambio(i, Q) = min(Cambio(i-1, Q), Cambio(i, Q - ci)+1)
Si (i?0) ó (Qɘ) entonces no existe ninguna solución al problema, y Cambio(i, Q) vale +?.
En otro caso para cualquier iɬ, Cambio(i, 0) = 0.
5.3.1. Problema del cambio de monedas.