Problema del cambio de moneda (II)

Se trata de, dada una serie de monedas, devolver una cantidad determinada usando el menor número posible. Vamos a aplicar la Programación Dinámica para evitar los errores que se pueden producir utilizando un Algoritmo Voraz.

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 establecer una tabla con una matriz M((i,j)=cambio(i,j) donde i indica el número total de monedas <=Xi para devolver la cantidad j. Entonces cambio(i,j) es: $$cambio(i-1,j) \hspace{0.1 cm}si \hspace{0.1 cm} X_i>j$$ $$min(cambio(i-1,j),cambio(i,j-X_k)+1) \hspace{0.2 cm} si X_i\leq j$$

En la tabla la primera fila está numerada de 0 a c y la primera columna con los valores de las monedas incluida la posibilidad de no tener monedas. La primera columna de ceros indica que no se necesita ninguna moneda para devolver cero. La fila de infinitos indica que sin monedas no podemos devolver ninguna cantidad. La columna de infinitos indica que no podemos devolver 1 con monedas de valor superior. 

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 !