El problema del cambio

Código en:JavaC#PythonJavaScript

En resumen: El problema del cambio busca el menor número de monedas que suman un importe; una tabla de programación dinámica lo resuelve en O(importe × monedas), nombra las monedas y cuenta las formas.

Problema

El cambio de la máquina

La máquina del estacionamiento devuelve el cambio. Tiene un tubo para cada una de las ocho monedas de euro: 1, 2, 5, 10, 20 y 50 céntimos, 1 € y 2 €. Cuantas menos monedas devuelva, menos veces tendrá que rellenar los tubos alguien. Por eso el cambio tiene que usar el menor número de monedas.

El desarrollador no quiere adivinar y escribe una recursión que lo prueba todo: para cada moneda que cabe en el cambio, «esta moneda más lo mejor para el resto», y se queda con la menor. Los importes están en céntimos, y el contador cuenta las monedas probadas:

static long tries = 0;

static int fewest(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    int best = amount + 1;
    for (int coin : coins) {
        if (coin > amount) {
            break;
        }
        tries++;
        int count = fewest(coins, amount - coin) + 1;
        best = Math.min(best, count);
    }
    return best;
}

int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
for (int amount : new int[] {10, 20, 30}) {
    tries = 0;
    int count = fewest(coins, amount);
    System.out.println(amount + " céntimos: " + count + " monedas, " + tries + " intentos");
}

Salida

10 céntimos: 1 monedas, 309 intentos
20 céntimos: 1 monedas, 66281 intentos
30 céntimos: 2 monedas, 14158888 intentos

Las respuestas son correctas. Pero para 30 céntimos la recursión prueba 14 158 888 monedas, y para 40 céntimos 3 024 560 419. Un cambio de 63 céntimos necesita 689 951 222 249 236 intentos: a mil millones por segundo son ocho días, mientras el conductor espera frente a la barrera.

La idea

La tabla

La recursión pregunta una y otra vez lo mismo: lo mejor para 13 céntimos, para 8 céntimos, para 3 céntimos. Son los subproblemas superpuestos de la lección anterior. Solo que aquí de cada importe salen hasta ocho ramas, una por moneda, y el árbol crece todavía más rápido.

Así que construimos una tabla de abajo hacia arriba. Una tabla de programación dinámica se describe con cuatro cosas:

• Qué significa la celda. best[a] es el menor número de monedas para exactamente a céntimos.
• De dónde viene. La última moneda es una de las que caben. Así que best[a] es 1 + best[a − moneda] para la mejor moneda.
• En qué orden se llena. a − moneda es menor que a. De izquierda a derecha, todo lo que lee la celda ya está hecho.
• Dónde está la respuesta. En la última celda, best[cambio]. El comienzo es best[0] = 0: cero céntimos no necesitan monedas.

Esto es una tabla DP: una celda para cada subproblema, llenada en un orden en el que cada celda encuentra listas las que necesita. Como en la lección anterior, la elección se hace solo dentro de la celda, entre varias opciones.

Míralo

Celda por celda

La tabla para 9 céntimos. Fíjate en las flechas: cada una viene de la celda a − moneda, y la celda a se queda con lo más pequeño que ha visto:

static List<Integer> change(int[] coins, int amount) {
    int[] best = new int[amount + 1];
    int[] last = new int[amount + 1];
    for (int a = 1; a <= amount; a++) {
        best[a] = amount + 1;
        for (int coin : coins) {
            if (coin > a) {
                break;
            }
            int count = best[a - coin] + 1;
            if (count < best[a]) {
                best[a] = count;
                last[a] = coin;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int a = amount; a > 0; a -= last[a]) {
        used.add(last[a]);
    }
    return used;
}

Paso a paso, en palabras

1. change(coins, 9): best[a] es el menor número de monedas para a céntimos, last[a] la moneda con la que se llega hasta allí. best[0] = 0: cero céntimos no necesitan monedas.
2. Para cada a de izquierda a derecha, prueba cada moneda hasta a: una moneda más lo mejor para el resto, best[a − moneda] + 1. La flecha viene de esa celda.
3. a = 5: la moneda 1 da best[4] + 1 = 3, la moneda 2 da best[3] + 1 = 3, la moneda 5 da best[0] + 1 = 1. La celda se queda con lo más pequeño, y last recuerda la moneda.
4. Las monedas están ordenadas de pequeña a grande, y 10 ya es más que 9: el bucle se detiene ahí. Cada celda lee solo celdas a su izquierda, que ya son definitivas.
5. Hacia atrás por last: 9 → 7 → 5 → 0. Las monedas son 2 + 2 + 5. 22 intentos para 9 céntimos, cada celda resuelta una vez.

int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
System.out.println(change(coins, 9));

Salida

[2, 2, 5]

amount + 1 significa «todavía nada»: nunca necesitas más monedas que céntimos, porque incluso las monedas de un céntimo suman exactamente amount. Así que el primer intento siempre es mejor. El número es pequeño y + 1 no puede desbordarse, como sí pasaría con Integer.MAX_VALUE.

La idea

Qué monedas

El número no basta: la máquina también tiene que saber qué monedas soltar. Por eso, junto a best[a], la tabla guarda también last[a], la moneda que lleva a lo mejor para a. Al final empiezas por el cambio: sueltas last[a], lo restas y repites hasta llegar a 0.

static long tries = 0;

static List<Integer> change(int[] coins, int amount) {
    int[] best = new int[amount + 1];
    int[] last = new int[amount + 1];
    for (int a = 1; a <= amount; a++) {
        best[a] = amount + 1;
        for (int coin : coins) {
            if (coin > a) {
                break;
            }
            tries++;
            int count = best[a - coin] + 1;
            if (count < best[a]) {
                best[a] = count;
                last[a] = coin;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int a = amount; a > 0; a -= last[a]) {
        used.add(last[a]);
    }
    return used;
}

int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
for (int amount : new int[] {63, 480}) {
    tries = 0;
    List<Integer> used = change(coins, amount);
    String list = used.stream().map(String::valueOf).collect(Collectors.joining(" + "));
    System.out.println(amount + " céntimos: " + list + ", " + tries + " intentos");
}

Salida

63 céntimos: 1 + 2 + 10 + 50, 296 intentos
480 céntimos: 10 + 20 + 50 + 200 + 200, 3460 intentos

296 intentos para 63 céntimos en lugar de 689 951 222 249 236. La tabla tiene una celda por céntimo, y cada celda prueba como máximo las ocho monedas. El trabajo es O(n · k): n céntimos por k clases de moneda. Con k = 8 es lineal en el cambio.

Pruébalo

Completa

Una moneda más lo mejor para el resto. ¿Qué celda lee el intento?

static List<Integer> change(int[] coins, int amount) {
    int[] best = new int[amount + 1];
    int[] last = new int[amount + 1];
    for (int a = 1; a <= amount; a++) {
        best[a] = amount + 1;
        for (int coin : coins) {
            if (coin > a) {
                break;
            }
            int count = best[] + 1;
            if (count < best[a]) {
                best[a] = count;
                last[a] = coin;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int a = amount; a > 0; a -= last[a]) {
        used.add(last[a]);
    }
    return used;
}

Comprobar

La idea

¿Por qué no la moneda más grande primero?

Un cajero hace otra cosa: da la moneda más grande que cabe y repite. Para 63 céntimos son 50, 10, 2, 1: otra vez cuatro monedas. Con monedas de euro, esta regla siempre da el menor número de monedas. Las monedas están elegidas así.

Pero la regla depende del sistema de monedas. Con otras monedas, o cuando se vacía un tubo de la máquina, «la más grande primero» puede dar más monedas de las necesarias. Cuándo funciona y cuándo falla es la lección «Cuándo falla un algoritmo voraz». La tabla no depende de eso: prueba cada moneda para cada importe y encuentra el menor número para cualquier moneda.

La idea

De cuántas formas

Otro problema con la misma tabla. El cajero automático paga importes con billetes de 5, 10, 20 y 50 €. Los testers quieren comprobar cada combinación posible para 100 € y preguntan: ¿cuántas hay?

Ahora la celda es count[a]: de cuántas formas se pueden formar exactamente a euros. count[0] = 1, la combinación vacía. El bucle exterior recorre los billetes, el interior los importes:

static long ways(int[] notes, int amount) {
    long[] count = new long[amount + 1];
    count[0] = 1;
    for (int note : notes) {
        for (int a = note; a <= amount; a++) {
            count[a] += count[a - note];
        }
    }
    return count[amount];
}

int[] notes = {5, 10, 20, 50};
System.out.println(ways(notes, 100) + " formas");

Salida

49 formas

El orden de los bucles importa. Cuando todos los de cinco van antes que los de diez, cada combinación se construye en un solo orden: primero los de cinco, luego los de diez. Así que 5 + 10 y 10 + 5 son la misma combinación y se cuentan una vez. Y aquí nadie busca un mínimo: la celda suma el número de formas de las celdas a su izquierda.

Pruébalo

Predice la salida

¿Cuántas combinaciones hay para 20 € con billetes de 5, 10 y 20?

static long ways(int[] notes, int amount) {
    long[] count = new long[amount + 1];
    count[0] = 1;
    for (int note : notes) {
        for (int a = note; a <= amount; a++) {
            count[a] += count[a - note];
        }
    }
    return count[amount];
}

int[] notes = {5, 10, 20};
System.out.println(ways(notes, 20) + " formas");

Respuesta

3 formas

6 formas

4 formas

Comprobar

Pruébalo

Encuentra el error

Un compañero escribió el mismo conteo, pero para 100 € sale un número mucho mayor:

int[] notes = {5, 10, 20, 50};
System.out.println(ways(notes, 100) + " formas");

Salida

48007 formas

¿Qué línea tiene el error?

Elige la línea con el error.

1static long ways(int[] notes, int amount) {2 long[] count = new long[amount + 1];3 count[0] = 1;4 for (int a = 1; a <= amount; a++) {5 for (int note : notes) {6 if (note <= a) {7 count[a] += count[a - note];8 }9 }10 }11 return count[amount];12}

Comprobar

Míralo

Mídelo: recursión frente a tabla

Contamos las monedas probadas: en cada llamada recursiva y en cada celda. La recursión no se ejecuta por encima de 30 céntimos: con 40 céntimos son más de 3 mil millones de intentos.

• Recursión sin memoria O(2ⁿ)
• Tabla O(n)

Algoritmo	n = 10	n = 20	n = 30
Recursión sin memoria	309	66.281	14.158.888
Tabla	26	67	117

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

static List<Integer> change(int[] coins, int amount) {
    int[] best = new int[amount + 1];
    int[] last = new int[amount + 1];
    for (int a = 1; a <= amount; a++) {
        best[a] = amount + 1;
        for (int coin : coins) {
            if (coin > a) {
                break;
            }
            int count = best[a - coin] + 1;
            if (count < best[a]) {
                best[a] = count;
                last[a] = coin;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int a = amount; a > 0; a -= last[a]) {
        used.add(last[a]);
    }
    return used;
}

Cada 10 céntimos la recursión se multiplica por unos 200, mientras que la tabla crece entre 40 y 50 intentos. La curva de la recursión lleva la etiqueta O(2ⁿ): es exponencial, con una base de aproximadamente 1,7.

Más precisamente, para curiosos

Los mismos números en tu lenguaje:

static long tries = 0;

static int fewest(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    int best = amount + 1;
    for (int coin : coins) {
        if (coin > amount) {
            break;
        }
        tries++;
        int count = fewest(coins, amount - coin) + 1;
        best = Math.min(best, count);
    }
    return best;
}

static List<Integer> change(int[] coins, int amount) {
    int[] best = new int[amount + 1];
    int[] last = new int[amount + 1];
    for (int a = 1; a <= amount; a++) {
        best[a] = amount + 1;
        for (int coin : coins) {
            if (coin > a) {
                break;
            }
            tries++;
            int count = best[a - coin] + 1;
            if (count < best[a]) {
                best[a] = count;
                last[a] = coin;
            }
        }
    }
    List<Integer> used = new ArrayList<>();
    for (int a = amount; a > 0; a -= last[a]) {
        used.add(last[a]);
    }
    return used;
}

int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
for (int amount : new int[] {10, 20, 30}) {
    tries = 0;
    fewest(coins, amount);
    long plain = tries;
    tries = 0;
    change(coins, amount);
    System.out.println(amount + " céntimos: sin memoria " + plain + ", tabla " + tries);
}

Salida

10 céntimos: sin memoria 309, tabla 26
20 céntimos: sin memoria 66281, tabla 67
30 céntimos: sin memoria 14158888, tabla 117

Ejercicio

El cambio de la entrada

Resuélvelo en tu editor.

Cambio. Lee el cambio en céntimos e imprime cuántas monedas devuelve la máquina y cuáles. Usa change de la lección.

Entrada

480

Salida

5 monedas: 10 + 20 + 50 + 200 + 200

Más tareas

• Un tubo vacío. Los tubos de 1 y 2 céntimos están vacíos. ¿Qué importes menores de 1 € no puede devolver la máquina de ninguna manera? ¿Cómo lo notas en la tabla? (Pista: la celda se queda en amount + 1.)
• La más grande primero. Imprime las monedas de la más grande a la más pequeña.
• De cuántas formas con monedas. ¿De cuántas formas puedes pagar 1 € con las monedas de 1 a 50 céntimos? ¿Y si también se permite la moneda de 1 €?

Más precisamente

Cambio imposible y números muy grandes

Dos cosas que la lección se saltó.

Más precisamente, para curiosos

Cuando el cambio no se puede devolver. Si los tubos de 1 y 2 céntimos están vacíos, 3 céntimos no se pueden devolver con nada. Entonces la celda se queda en amount + 1, porque ningún intento es mejor. Y si last[a] es 0, volver atrás giraría eternamente en el mismo sitio. Por eso, antes de volver atrás, compruebas si best[amount] > amount, y la máquina dice «Sin cambio, por favor pague el importe exacto».

El número de formas crece muy rápido. ¿De cuántas formas puedes pagar 100 € solo con monedas (10 000 céntimos, las ocho monedas de euro)?

static long ways(int[] notes, int amount) {
    long[] count = new long[amount + 1];
    count[0] = 1;
    for (int note : notes) {
        for (int a = note; a <= amount; a++) {
            count[a] += count[a - note];
        }
    }
    return count[amount];
}

int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
System.out.println(ways(coins, 10000));

Salida

1133873304647601

Eso es más de mil billones. int llega hasta unos 2100 millones y se habría desbordado hace mucho, sin error. Por eso la tabla es long. Para importes aún mayores tampoco long basta (unos 9,2 · 10¹⁸) y necesitas `BigInteger`.

La tabla en dos dimensiones. Contar las formas es en realidad una tabla «los primeros i billetes × el importe»: la celda (i, a) dice de cuántas formas se puede formar a solo con los primeros i billetes. La fila i se construye a partir de la fila de arriba (sin el billete i) y de la celda de la izquierda en la misma fila (con un billete i más). El programa guarda una sola fila y la sobrescribe de izquierda a derecha. Por eso el bucle exterior recorre los billetes: recorre las filas. La misma idea, una fila en lugar de toda la tabla, vuelve en el problema de la mochila.

Test

Ponte a prueba

1. ¿Qué significa la celda best[a] en la tabla del cambio?

La moneda más grande que cabe en aEl menor número de monedas que suman exactamente a céntimosCuántas monedas de valor a tiene la máquina

2. ¿Por qué la tabla se llena de izquierda a derecha, desde a = 1?

El orden no importa, de derecha a izquierda también funcionaPorque las monedas están ordenadas de izquierda a derechaLa celda a solo lee celdas a − moneda, que están a su izquierda y ya son definitivas

3. ¿Cómo dice la tabla qué monedas son, y no solo cuántas?

No puede: hace falta una segunda tabla para cada monedalast[a] recuerda la moneda que lleva a lo mejor para a; si vuelves atrás desde el cambio siguiendo last, obtienes las monedas una por unaCuenta cuántas veces se usó cada celda

4. En el conteo de formas los bucles están cambiados: el exterior recorre los importes y el interior los billetes. ¿Qué pasa?

Nada, la respuesta es la mismaCuenta menos formasCuenta secuencias: 5 + 10 y 10 + 5 pasan a ser dos formas, así que el número es mucho mayor

5. Con monedas de euro, «la moneda más grande que quepa, y otra vez» da el menor número de monedas. Entonces, ¿para qué una tabla?

La tabla da el menor número de monedas para cualquier moneda, mientras que la regla voraz tiene sistemas de monedas en los que fallaLa regla voraz no funciona con monedas de euroLa tabla es más rápida que la regla voraz

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Big-O: cómo crece el trabajo · Complejidad en espacio · Divide y vencerás y el árbol de recursión · Subproblemas superpuestos
• Continúa en: El problema de la mochila · La subsecuencia común más larga y diff · Reconocer un problema de DP · Algoritmos voraces y cuándo funcionan
• Ejercicios sobre el tema: Programación dinámica