Presentación

Continuamos la sesión con un problema que puede ser reducido a un problema clásico en programación dinámica. Se trata del problema de calcular de cuántas formas puede pagarse una cierta cantidad de dinero habida cuenta de las cantidades disponibles en monedas y billetes. Este ejercicio se corresponde con el problema 147 del juez on-line de la UVA:

PROBLEMA 147. Dollars: Enunciado del problema en el juez on-line de la UVA

Al igual que hicimos con el primer problema, vamos a detenernos en este punto a estudiar el enunciado en la página del juez on-line antes de continuar, de modo que en lo que sigue supondremos que el problema ha sido al menos leído y comprendido.

Si el alumno se siente capaz, puede intentar resolver el problema sin seguir leyendo más adelante el análisis que sigue a continuación.

Continuar con la lectura del análisis del problema y su enunciado.

Análisis del problema y su enunciado

Este problema puede ser reducido al clásico problema de programación dinámica conocido como el problema de la suma de subconjunto, en su variante de conteo de dinero (Problem C, en la referencia del enlace anterior). El problema original de la suma del subconjunto es determinar dentro de un cierto conjunto finito de valores enteros V = {a₁, …, a_n}, si existe un subconjunto S ⊆ V tal que la suma de los elementos de S es igual a un cierto valor T fijo y conocido de antemano (típicamente T = 0).

La variante del problema de conteo de dinero difiere del problema anterior en que los valores del conjunto V son mayores que cero y que cada elemento a_i puede sumarse un número arbitrario y natural de veces k_i para obtener el número objetivo T:

Una vez identificado el problema, sabemos que existe una expresión en forma de función recurrente que podemos explotar para nuestros propósitos de aplicar la técnica de programación dinámica. Sea C(i, T) el número de maneras de sumar la cantidad T utilizando las cantidades {a₁, …, a_i} ⊆ V. La expresión de la función C(i, T) es simplemente:

Donde podemos tomar los siguientes casos base:

• C(0, T) = 0,     para T < 0
• C(i, 0) = 1,     para i ≥ 0

En este caso nos encontramos con la dificultad de que el segundo parámetro de la función C en general no es un valor entero, lo cual nos dificultará (aunque no mucho) la aplicación de la técnica de programación dinámica, pues necesitaremos que estos valores sean índices de tablas.

En este enunciado podemos encontrar algunos datos significativos que nos pueden servir de ayuda para la resolución del ejercicio:

• Se nos dice que el valor máximo para la cantidad de dinero es 300$.
• Se nos dice que todos los valores serán múltiplos de 5¢.

Continuar leyendo pistas de resolución del ejercicio.

Primera pista:

El primer escollo que vamos a estudiar cómo superar es el hecho de que el segundo parámetro de la función recurrente C(i, T) no es un valor entero. Los valores del conjunto V son los siguientes:

La cuestión es convertir el problema en otro equivalente en el que estas cantidades sean enteras. Puesto que hablamos de cantidades del orden de la centésima, podríamos pensar en escalar el problema multiplicando por 100 todas las cantidades que intervienen en el mismo. Esto significaría que la cantidad máxima pasaría de 300 a 30.000, y los valores de las unidades monetarias pasarían a ser las siguientes:

Si hacemos este escalado, significa que la tabla que empleamos debería ser de un tamaño de 30.000 × 11. No es un tamaño exagerado, pero podemos intentar hacerla más pequeña. La cuestión es buscar el factor más pequeño que convierta en enteras todas las cantidades presentes. En este caso, ese factor es 20, lo cual provocaría que la cantidad máxima pasaría de 300 a 6.000, y los valores de las unidades monetarias pasarían a ser las siguientes :

Con este otro escalado, la tabla que empleamos tendrá un tamaño de 6.000 × 11, lo cual es sensiblemente menor que con el caso anterior.

Continuar leyendo la siguiente pista para de resolución del ejercicio.

Segunda pista:

Con el análisis realizado y el escalado propuesto en la pista anterior ya tenemos las herramientas necesarias para escribir una primera versión del programa que resuelve este problema. Más abajo en esta misma pista dejamos el listado de un programa basado en este enfoque.

Sin embargo, todavía podemos realizar alguna mejora de eficiencia, en este caso respecto al recurso memoria. Podemos comprobar que los elementos que realmente nos interesan de la tabla que define la función recurrente C(i, T) son los de la última fila. En efecto, lo que el problema nos pide no son las formas de descomponer una cierta cantidad en unidades monetarias que sean un subconjunto de la totalidad, sino con todas ellas. Si además observamos nuevamente la forma de la recursión de la función C(i, T):

, podemos comprobar que cada valor C(i, T) depende del valor en la misma columna T pero en la fila anterior (valor C(i-1, T)) y de otro valor que está en la misma fila pero en columnas anteriores (valor C(i, T-a_i)). Esto sugiere que podríamos utilizar una única fila de esta tabla en la que diésemos tantas iteraciones como filas hay en la tabla original, y en cada paso calculemos el valor C(T) en función de su propio valor anterior y de otros valores ya calculados en la misma pasada actual.

Proponemos al alumno resolver el problema con este nuevo enfoque y a continuación presentamos un programa C que lo resuelve con una tabla bidimensional:

Programa C con tabla bidimensional:

#include <stdio.h>

#define N_MONEDAS   11
#define LONG_TABLA  6000

int monedas [N_MONEDAS] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};
unsigned long long int C[N_MONEDAS][LONG_TABLA + 1];


int main (void)
{
    int i, j;
    double cantidad;

    for (i = 0; i < N_MONEDAS; i++)
        for (j = 0; j <= LONG_TABLA; j++)
            C[i][j] = 0;

    for (i = 0; i < N_MONEDAS; i++)   C[i][0] = 1;
    for (j = 0; j <= LONG_TABLA; j++) C[0][j] = 1;

    for (i = 1; i < N_MONEDAS; i++) {
        for (j = 0; j < monedas[i]; j++)
            C[i][j] = C[i-1][j];
        for (j = monedas[i]; j <= LONG_TABLA; j++)
            C[i][j] = C[i-1][j] + C[i][j - monedas [i]];
    }

    while (scanf ("%lf", &cantidad), cantidad > 0.0) {
        j = (int) (cantidad * 20.0);
        printf ("%6.2lf%17lu\n", cantidad, C[N_MONEDAS-1][j]);
    }

    return 0;
}

Ver el listado del programa que resuelve el problema con una tabla unidimensional.

Listado del programa:

Programa C++:

#include <iostream>
#include <iomanip>

#define N_MONEDAS   11
#define LONG_TABLA  6000

using namespace std;

int monedas [N_MONEDAS] = {1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000};
unsigned long long int C[LONG_TABLA + 1];


int main (void)
{
    C[0] = 1;
    for (int j = 1; j <= LONG_TABLA; j++) C[j] = 0;

    for (int i = 0; i < N_MONEDAS; i++ )
        for (int j = monedas [i]; j <= LONG_TABLA; j++)
                C[j] += C[j - monedas[i]];

    double cantidad;

    cout << setiosflags (ios::fixed) << setprecision(2);
    while (cin >> cantidad, cantidad > 0.0) {
        int j = (int) (cantidad * 20.0);
        cout << setw(6)  << cantidad
             << setw(17) << C[j]
             << endl;
    }

    return 0;
}

Programa Pascal:

program p147;

const

    N_MONEDAS  = 11;
    LONG_TABLA = 6000;

type
    TRango_Monedas  = 1 .. N_MONEDAS;
    TRango_Cantidad = 0 .. LONG_TABLA;
    TTabla_Monedas  = array [TRango_Monedas]  of Integer;
    TTabla_Cantidad = array [TRango_Cantidad] of QWord;

const
    Tabla_Monedas : TTabla_Monedas =
        (1, 2, 4, 10, 20, 40, 100, 200, 400, 1000, 2000);

var
    i : TRango_Monedas;
    j : TRango_Cantidad;
    t : TTabla_Cantidad;
    x : Double;

begin
    t[0] := 1;
    for j := 1 to LONG_TABLA do t[j] := 0;

    for i := 1 to N_MONEDAS do
        for j := Tabla_Monedas[i] to LONG_TABLA do
            t[j] := t[j] + t[j - Tabla_Monedas[i]];

    read (x);
    while x > 0.0 do
    begin
        j := round (x * 20.0);
        writeln (x:6:2, t[j]:17);
        read (x)
    end
end.

Olimpiada de programación - Facultad de Informática - Universidad de Murcia