Existen n monedas diferentes y con una cantidad ilimitada de cada tipo:
$$X_1 < X_2 < X_3 \cdots < X_n$$
Se trata de devolver una cantidad c, donde cambio(n,c) indica las mínimas monedas necesarias para devolver c usando X1, X2, X3,...Xn monedas.
- Si Xn>c no usamos esa moneda y cambio(n,c)=cambio(n-1,c).
- Si Xn<=c podemos usar esa moneda o no.
- Si usamos Xn entonces cambio(n,c-Xn)+1.
- Si no usamos Xn entonces cambio(n-1,c).
- De las dos opciones cogemos la menor cantidad.
Vamos a explicar como se obtiene el elemento M(3,7) (verde) de la matriz. Para ello utilizamos los elementos M(2,7) M(3,4) (rojos)
$$cambio(3-1,7)=M(2,7)=3 \hspace{0.2 cm} cambio(3,7-3)+1=M(3,4)+1=2$$
Al ser M(2,7)=3 se retroceden 3 posiciones desde la columna 7. De los dos valores obtenidos el menor es el que se asigna al elemento M(3,7). El razonamiento seguido, para todos los demás elementos de la matriz, es el mismo. El último elemento M(4,9) indica el número de monedas necesaria.
¡Por tanto la solución óptima utiliza 3 monedas!
Vamos a ver el reparto de esas tres monedas. Para ello aplicamos el algoritmo siguiente:
$$ si \hspace{0.2 cm} i>2 \land M(i,j)=M(i-1,j) \rightarrow i=i-1$$
$$ si \hspace{0.2 cm} no \rightarrow N(i)=N(i)+1 \land j=j-X_i$$
Empezamos en el último elemento M(4,8). Como M(4,8)=M(3,8)=3 subimos una fila y ahora M(3,8)=3<>M(2,8)=4 entonces el contador de monedas de valor 3 es N(3)=1 y retrocedemos 8-3 columnas y se repite el proceso a partir del elemento M(3,5) (verde) consiguiendo una segunda moneda de 3 y finalmente una moneda de 2.
¡Por tanto con 2 monedas de 3 y una de 2 se devuelve la cantidad 8 !
