Programación dinámica: algoritmo cambio monedas con tipo de monedas a devolver

Este algoritmo de programación dinámica calcula el número  de monedas a retornar de una cantidad dada, asi como la cantidad de cada tipo de moneda. Para ello pasaremos como parámetro la cantidad a retornar y un vector con el valor de  los diferentes tipos de monedas. Finalmente el algoritmo retorna un vector con la cantidad de cada tipo de monedas a devolver.

Problema

En primer lugar debemos pensar como plantear el problema de forma incremental. Consideramos el tipo de moneda de mayor valor, XN. Si XN > C entonces la descartamos y pasamos a considerar monedas de menor valor. Si XN < C tenemos dos opciones:  o tomar una moneda de tipo XN, Y completar la cantidad restante C – XN con otras monedas, o no tomar ninguna moneda de tipo XN Y completar la cantidad C con monedas de menor valor. De las dos opciones nos quedamos con la que requiera un número menor de monedas. El problema lo podemos expresar de la siguiente forma cuando consideramos N tipos de monedas:

Cambio (N,C ) =

cambio(N – 1,C) si XN > C
MIN{cambio(N-1, C), cambio(N, C – XN) + 1) si XN <= C

Podemos razonar análogamente para monedas de valores k menores que N y para cantidades

C’ menores que C:

Cambio(k,C’)

Cambio(k-1 , C’) si xk  > C’
Min{cambio(k-1,C’),cambio(N,C’-xk)+1) si k >=C’

Llegamos a los casos base de la recurrencia cuando completamos la cantidad C:

cambio(k,0) = 0 si 0<= k <=n  ,

o cuando ya no quedan más tipos de monedas por considerar, pero aún no se ha completado la cantidad C:

cambio(0,C’) = ∞ si 0< C’ <= C

Podemos construir una tabla para almacenar los resultados parciales que tenga una fila para cada tipo de moneda y una columna para cada cantidad posible entre 1 y C. Cada posición t[i,j] será el número mínimo de monedas necesario para dar una cantidad j con 0 <= j <= c utilizando sólo monedas de los tipos entre 1 e i, con 0 <=i<=n . La solución al problema será por tanto el contenido de la casilla t[N,C]. Para construir la tabla empezamos rellenando los casos base t[i ,0] = 0, para todo i con 0 <= i  <=  n . A continuación podemos rellenar la tabla bien por filas de izquierda a derecha, o bien por columnas de arriba a abajo.

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 N (12 en este caso) . 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:

 

0

1

2

3

4

5

6

7

8

9

10

11

12

x = 1

0

1

2

3

4

5

6

7

8

9

10

11

12

x = 6

0

1

2

3

4

5

1

2

3

4

5

6

2

x = 10

0

1

2

3

4

5

1

2

3

4

1

2

2

Ejemplo

En el caso anterior hay que pagar 12 con monedas de 1,6,10. Supongamos que queremos pagar 12 o pagamos con 12 monedas de 1 , o 2 monedas de 6  o con una de 10, y 2 de 1. Como la mejor opción es la de las monedas de 6 me quedo con esa y es la que marco en la tabla. Observese que a pesar de que con monedas de 10 me haría falta 3 monedas marco solo 2 porque es la mejor opción

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.

Saber qué tipo de monedas hay que devolver

Partimos de la casilla final. Para cada casilla t[i,j] el algoritmo va comprobando si su valor ha variado respecto a la casilla de la fila superior. Si no ha variado podemos deducir que no se ha empleado ninguna moneda del tipo de la fila i, y pasamos a comprobar la casilla superior t[i-l j].  Si ha variado, anotamos que se ha utilizado una moneda de ese tipo Xi y nos movemos a la casilla t[i, j-moneda[i]], para ver qué monedas se han utilizado para dar la cantidad restante. Siguiendo esta estrategia terminaremos alcanzando la casilla t[0,0] en la que ya no queda ninguna cantidad pendiente. Esto se hace en el método seleccionMonedas()

Resumiendo si tenemos un vector con los tipos de monedas {1,6,10} y queremos saber la cantidad de monedas necesarias para dicho cambio y que tipo de monedas es, el vector que retornara será {0,2,0} es decir 0 monedas de la cantidad 1, 2 monedas de la cantidad 6 y 0 monedas de la cantidad 10.

Coste

Para estudiar el coste del algoritmo calculamos el tamaño de la tabla que hay que construir: N x (C + 1). Como las operaciones aritméticas involucradas son de coste constante,  el tiempo de ejecución está en O(NC).

Implementación en Java

public class Cambio
{
    private int[][] matrizCambio;
    private int[] vectorMonedas;
    private int cantidad;
    private int[] vectorSeleccion;

    Cambio(int cantidad, int[]  monedas){
        this.cantidad = cantidad;
        this.vectorMonedas = monedas;
        matrizCambio = calcularMonedas(cantidad, monedas);
        vectorSeleccion = seleccionarMonedas(cantidad, monedas, matrizCambio);
    }
    public int[] getVectorSeleccion(){
        return this.vectorSeleccion;
    }
    private int[][] calcularMonedas(int cantidad, int[]  monedas){

        int[][] matrizCambio = new int[monedas.length + 1][cantidad + 1];

        for (int i = 0; i < monedas.length; i++)
            matrizCambio[i][0] = 0;

        for (int j = 1; j <= cantidad; j++)
            matrizCambio[0][j] = 99;

        for (int i = 1; i <= monedas.length; i++)
            for (int j = 1; j <= cantidad; j++) {
                if (j < monedas[i - 1]) {

                    matrizCambio[i][j] = matrizCambio[i - 1][j];
                } else {

                    int minimo = 0;

                    minimo = min(matrizCambio[i - 1][j] , matrizCambio[i][j- monedas[i - 1]] + 1);
                    matrizCambio[i][j] = minimo;

                }
            }

         return matrizCambio;
        }
    private int[] seleccionarMonedas(int c, int[] monedas, int[][]tabla ){
        int i,j;
        int[] seleccion = new int[monedas.length];
        for(i = 0; i< monedas.length; i++){             seleccion[i]=0;         }         i= monedas.length;         j= c;         while(j>0){
            if(i>1 && tabla[i][j]==tabla[i-1][j]){
                i--;
            }
            else{
                seleccion[i-1]++;
                j = j - monedas[i-1];
            }
        }

        return seleccion;
    }

    private int min(int a, int b){
        if(a<b)
            return a;

        else 
            return b;
    }

}

Para llamar a la clase con el ejemplo citado anteriormente hariamos :

Cambio c = new Cambio(12, new int[]{1,6,10})

y con c.getVectorSeleccion(); obtendriamos el vector con las cantidades de cada moneda cuyo indice se corresponde con los tipos de monedas que pasamos al contructor.

About these ads

Acerca de Juan Camba

10001011
Esta entrada fue publicada en Algoritmos, Java y etiquetada , , , , , , , , . Guarda el enlace permanente.

4 respuestas a Programación dinámica: algoritmo cambio monedas con tipo de monedas a devolver

  1. manuel dijo:

    Muy bueno podrias explicar como imprimir la tabla

    • Juan Camba dijo:

      HOla Manuel, No vi tu coment, lo podes hacer con un metodo al cual le pasas por parametro la matriz que queres imprimir y te retorna la matriz en formato string el cual se lo pasas al system.out.println, se entiende ?

      private String matrizToString(int [][] matriz){
      		
      		int f= matriz.length;
      		int c= matriz[0].length;
      		String str = "";
      		
      		for(int i = 0; i< f;i++){
      			for(int j=0; j<c; j++){
      				str += "["+matriz[i][j]+"]";
      			}
      			str +="\n";
      		}
      		
      		return str;
      	}
      
  2. John dijo:

    Disculpe .. pero que pasa si tengo un numero limitado de monedas de cada valor

    • Juan Camba dijo:

      Así a lo loco te puedo decir que tienes que agregar otro vector con los mismos elementos que tipos de monedas diferentes tienes. Para el ejemplo explicado serian 3 elementos. Luego los valores del vector sería la cantidad de monedas de cada tipo. Por ejemplo si tienes los tipos de monedas [1,4,5] un vector cantidadTipo podría ser [2,4,8] donde te dice que del tipo 1 te quedan 2 monedas, del tipo 4 te quedan 4 monedas y del tipo 5 te quedan 8. Luego cada vez que entregas una moneda restas la cantidad al vector cantidadTipo. Si no tienes monedas es decir si es <= 0 puedes sacar un mensaje, o lanzar una excepción.
      Saludos

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s