El problema del cambio
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:
tries = 0
def fewest(coins, amount): global tries if amount == 0: return 0 best = amount + 1 for coin in coins: if coin > amount: break tries += 1 count = fewest(coins, amount - coin) + 1 best = min(best, count) return best
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [10, 20, 30]: tries = 0 count = fewest(coins, amount) print(f"{amount} céntimos: {count} monedas, {tries} intentos")10 céntimos: 1 monedas, 309 intentos20 céntimos: 1 monedas, 66281 intentos30 céntimos: 2 monedas, 14158888 intentosLas 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:
def change(coins, amount): best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return usedPaso a paso, en palabras
- 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.
- 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.
- 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.
- 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.
- 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.
coins = [1, 2, 5, 10, 20, 50, 100, 200]print(change(coins, 9))[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.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.
tries = 0
def change(coins, amount): global tries best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break tries += 1 count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return used
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [63, 480]: tries = 0 used = change(coins, amount) text = " + ".join(map(str, used)) print(f"{amount} céntimos: {text}, {tries} intentos")63 céntimos: 1 + 2 + 10 + 50, 296 intentos480 céntimos: 10 + 20 + 50 + 200 + 200, 3460 intentos296 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?
def change(coins, amount):
best = [0] * (amount + 1)
last = [0] * (amount + 1)
for a in range(1, amount + 1):
best[a] = amount + 1
for coin in coins:
if coin > a:
break
count = best[] + 1
if count < best[a]:
best[a] = count
last[a] = coin
used = []
a = amount
while a > 0:
used.append(last[a])
a -= last[a]
return usedEl resto después de la moneda son a - coin céntimos, y lo mejor para eso ya está en la tabla, porque queda a la izquierda. Una moneda más es + 1.
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:
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]notes = [5, 10, 20, 50]print(ways(notes, 100), "formas")49 formasEl 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?
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]
notes = [5, 10, 20]print(ways(notes, 20), "formas")Uno de veinte; dos de diez; uno de diez y dos de cinco; cuatro de cinco. Cuatro combinaciones. 6 es el número de secuencias: 10 + 5 + 5, 5 + 10 + 5 y 5 + 5 + 10 son tres de ellas, pero la combinación es una.
Pruébalo
Encuentra el error
Un compañero escribió el mismo conteo, pero para 100 € sale un número mucho mayor:
notes = [5, 10, 20, 50]print(ways(notes, 100), "formas")48007 formas¿Qué línea tiene el error?
Elige la línea con el error.
El bucle exterior recorre los importes y el interior los billetes. Así, para cada importe se prueba cada billete como el último, sin importar los anteriores, y cada disposición de una combinación se cuenta por separado: 5 + 10 y 10 + 5 son dos formas. Ese es el número de secuencias, 48 007, mientras que las combinaciones son 49. Cuando los billetes son el bucle exterior, cada combinación se construye en un solo orden y se cuenta una vez.
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 |
def change(coins, amount): best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return usedCada 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:
tries = 0
def fewest(coins, amount): global tries if amount == 0: return 0 best = amount + 1 for coin in coins: if coin > amount: break tries += 1 count = fewest(coins, amount - coin) + 1 best = min(best, count) return best
def change(coins, amount): global tries best = [0] * (amount + 1) last = [0] * (amount + 1) for a in range(1, amount + 1): best[a] = amount + 1 for coin in coins: if coin > a: break tries += 1 count = best[a - coin] + 1 if count < best[a]: best[a] = count last[a] = coin used = [] a = amount while a > 0: used.append(last[a]) a -= last[a] return used
coins = [1, 2, 5, 10, 20, 50, 100, 200]for amount in [10, 20, 30]: tries = 0 fewest(coins, amount) plain = tries tries = 0 change(coins, amount) print(f"{amount} céntimos: sin memoria {plain}, tabla {tries}")10 céntimos: sin memoria 309, tabla 2620 céntimos: sin memoria 66281, tabla 6730 céntimos: sin memoria 14158888, tabla 117Ejercicio
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.
4805 monedas: 10 + 20 + 50 + 200 + 200Má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)?
def ways(notes, amount): count = [0] * (amount + 1) count[0] = 1 for note in notes: for a in range(note, amount + 1): count[a] += count[a - note] return count[amount]
coins = [1, 2, 5, 10, 20, 50, 100, 200]print(ways(coins, 10000))1133873304647601long, y int se desbordaría sin error.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