Problema de las monedas con programación dinámica

De Wikipedia, la enciclopedia libre

Se ha sugerido que este artículo o sección sea fusionado con Problema de las monedas con programacion dinamica. (Discusión).

Este artículo o sección necesita ser wikificado con un formato adecuado a las convenciones de estilo de Wikipedia.
Por favor, edítalo para cumplir con ellas. No elimines este aviso hasta que lo hayas hecho. ¡Colabora wikificando!

Este artículo debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico.
Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla.

Se necesita crear un algoritmo que permita a una máquina expendedora devolver el cambio mediante el menor número de monedas posible. Mediante la Programación dinámica (computación) se solucionará el caso en el que el número de monedas de cada tipo es ilimitado. En el Problema de las monedas mediante el algoritmo voraz se puede consultar una manera de resolver el caso en el que el número de monedas es ilimitado.

[editar] Ejemplo

Supongamos que se tienen monedas de valor 1, 4 y 6 y que se debe devolver una cantidad correspondiente al valor 8. Siguiendo el método de la programación dinámica, se rellenará una tabla con las filas correspondientes a cada valor para las monedas y las columnas con valores desde el 1 hasta el 8. Cada posición (i, j) de la tabla nos indica el número mínimo de monedas requeridas para devolver la cantidad j con monedas con valor menor o igual al de i:

	1	2	3	4	5	6	7	8
m1=1	1	2	3	4	5	6	7	8
m2=4	1	2	3	1	2	3	4	2
m3=6	1	2	3	1	2	1	2	2

[editar] Algoritmo

1. Para cada casilla de la tabla hacer:
     - Si el valor de la moneda actual es mayor que la cantidad, se paga con el resto de monedas,
     es decir, se toma el resultado de la casilla superior.
     - Si el valor de la moneda actual es menor o igual que la cantidad, se toma el mínimo entre:
         > Pagar con el resto de monedas, tomando el resultado de la casilla superior.
         > Pagar con una moneda del tipo actual y el resto con el resultado que se hubiera obtenido
           al pagar la cantidad actual a la que se le ha restado el valor de la moneda actual.
2. Tomar como resultado el valor de la última celda.

[editar] Descripción detallada

Como parámetros de entrada, la función toma C, que corresponde con la cantidad a devolver, y un vector M de monedas, que almacena el valor de cada tipo. Devuelve num, el número de monedas necesarias para realizar la devolución.

fun cambio (C: nat; M[1..n] de nat) dev num: nat
var
       T[0..n][0..n] de nat
begin
       T[0][1..C] :=  ;
       T[1..n][0] := 0;
       para i := 1 hasta n hacer
           para j := 1 hasta C hacer
               si M[i] > j entonces T[i, j] := T[i-1, j]
                   si no
                       T[i, j] := min {T[i-1, j], T[i, j-M[i]] + 1 }
                   fsi
           fpara
       fpara
       num := T[n, C]
ffun

[editar] Complejidad

El algoritmo visto tiene complejidad $\Theta \left ( \mbox{n}\cdot\mbox{C} \right )$ en espacio y en tiempo, ya que se requiere una matriz de tamaño n*C, y los dos bucles anidados realizan exactamente ese número de iteraciones.