Programación dinámica/Problema de las monedas con programación dinámica

Esta página se ha identificado como una «hoja suelta» de algún wikilibro. Esta hoja se ha marcado con la categoría Wikilibros:Hojas sueltas y se debe integrar al wikilibro correspondiente.

Plantilla:A wikilibros Para el problema de las monedas con programación dinámica 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 se solucionará el caso en el que el número de monedas de cada tipo es limitado. Y mediante un algoritmo voraz, el caso en el que el número de monedas es ilimitado.

Descripción

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

Ejemplo para la posición i = 2 y j = 7, se requiere una moneda tipo 2 con valor 4 y tres monedas de tipo 1 con valor uno, por lo tanto en la tabla el número de monedas en la posición (2,7) sera 1 + 3 = 4.

Algoritmo

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:
1. Pagar con el resto de monedas, tomando el resultado de la casilla superior.
2. 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.
Tomar como resultado el valor de la última celda.

Pseudocódigo

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..C] de nat
begin
       T[0][1..C] :=  $\infty$ ;
       T[0..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

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.

La complejidad espacial puede reducirse a $\Theta \left({\mbox{C}}\right)$ ya que, en cada iteracion, solo necesitamos los datos almacenados en dos filas de la matriz (las filas i e i-1).

Véase también