El problema del cambio de monedas

Un cajero que da el cambio coge la moneda más grande que cabe, luego la siguiente, y con euros o dólares eso siempre da el mínimo de monedas. Pero si las monedas son 1, 3 y 4, la misma costumbre paga 6 con tres monedas cuando bastarían dos. La programación dinámica encuentra el verdadero mínimo para cualquier conjunto de monedas.

Una fila de cantidades, cada una con el mínimo de monedas que la forman, sobre monedas de tres tamaños distintos
Una fila de cantidades, cada una con el mínimo de monedas que la forman, sobre monedas de tres tamaños distintos

Dos preguntas

El problema del cambio de monedas tiene dos variantes. La primera pide el mínimo de monedas que forman una cantidad exacta; también se conoce como problema del cambio. La segunda pregunta cuántas combinaciones distintas de monedas la forman. En ambas, cada tipo de moneda se puede usar tantas veces como se quiera, y las dos se resuelven construyendo la respuesta para cada cantidad a partir de las respuestas para cantidades más pequeñas.

Mínimo de monedas, paso a paso

Haz una fila de celdas para las cantidades desde 0 hasta el objetivo. La cantidad 0 necesita 0 monedas; todas las demás empiezan en infinito. Recorre las cantidades en orden y, para cada una, prueba cada moneda c que quepa: la celda de la cantidad menos c, más una moneda, es un candidato. Quédate con el más pequeño. Cada celda depende solo de celdas a su izquierda, que ya son definitivas, así que una sola pasada llena la fila.

Un ejemplo

Con las monedas 1, 3 y 4: la cantidad 1 necesita 1 moneda, 2 necesita 2, 3 necesita 1 (una sola moneda de 3) y 4 necesita 1. Para 5, prueba 1 (4 necesita 1, así que 2 monedas), 3 (2 necesita 2, así que 3 monedas) y 4 (1 necesita 1, así que 2 monedas): lo mejor es 2. Para 6, prueba 1 (5 necesita 2, así que 3), 3 (3 necesita 1, así que 2) y 4 (2 necesita 2, así que 3): lo mejor es 2, con 3 + 3. El voraz habría pagado 4 + 1 + 1.

Contar las formas

Para contar combinaciones, añade las monedas de una en una. Con solo la primera moneda, cada cantidad se puede obtener de una forma o de ninguna. Cuando entra una moneda nueva c, las formas de obtener una cantidad a son las formas anteriores, sin c, más las formas de obtener a − c con c permitida otra vez, porque cada una de ellas se convierte en una forma de obtener a al añadir otra c. Con las monedas 1, 2 y 5 hay 4 formas de obtener 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 y 1 + 1 + 1 + 1 + 1.

Cuándo basta el método voraz

Un sistema de monedas en el que el voraz siempre da el mínimo de monedas se llama canónico. La mayoría de las monedas modernas están diseñadas así, y en 1994 David Pearson describió una prueba que comprueba un sistema de monedas en un número de pasos que solo crece de forma polinómica con el número de monedas. Las antiguas monedas británicas no eran canónicas: el voraz paga 48 peniques con una media corona, un chelín y un sixpence, cuando bastarían dos florines.

Explóralo

Abre la aplicación, cambia a la vista Tabla y pulsa Paso. En el modo Mínimo de monedas, la celda naranja es la cantidad que se está calculando y la celda azul es la cantidad menor que deja la moneda; la fila de abajo guarda la última moneda, y al final las monedas se leen de vuelta a lo largo de ella. Cambia a Número de formas y mira cómo crecen los recuentos fila a fila a medida que entra cada moneda.

Preguntas frecuentes

¿Es el problema del cambio de monedas un problema de la mochila?

Un pariente cercano. La variante del mínimo de monedas es un problema de la mochila no acotada en el que cada moneda es un objeto cuyo peso es su valor nominal, la mochila debe llenarse exactamente y el objetivo es usar el menor número de objetos.

¿Cuál es la complejidad temporal?

O(k·A) para k tipos de monedas y una cantidad A, en ambas variantes. La tabla del mínimo de monedas tiene A + 1 celdas, y la de las formas (k + 1)·(A + 1), aunque basta con una sola fila si las celdas se actualizan en el sitio.

¿Por qué contar las monedas en un orden fijo?

Si cada cantidad probara cada moneda, 1 + 2 y 2 + 1 se contarían como dos formas. Añadir las monedas fila a fila hace que una combinación siempre se construya primero con las monedas anteriores, así que cada una se cuenta exactamente una vez.

¿Se pueden leer de vuelta las monedas para el número de formas?

No como una única respuesta, porque hay muchas. La variante del mínimo de monedas guarda la última moneda de cada cantidad, y eso basta para reconstruir una combinación óptima.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Probar el cambio de monedas