Ver el código de «Programación dinámica/Problema de las monedas con programación dinámica»

{{hoja suelta}}
{{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 (computación)|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:

{| class="prettytable"
|- 
|  || 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:
## 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.
# 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] := <math>\infty</math>;
        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]] <math>\Theta \left ( \mbox{n}\cdot\mbox{C} \right )</math> 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 <math>\Theta \left ( \mbox{C} \right )</math> 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 ==

* [[Programación dinámica/Problema de la mochila con programación dinámica|Problema de la mochila con programación dinámica]]
* [[Problema del Cambio de Palabra Programación Dinámica en JAVA]]

[[Categoría:Algoritmia]]
[[Categoría:Optimización|P]]
[[Categoría:Investigación Operativa|P]]