Monedas usadas
Cantidad obtenida
Mínimo posible

    Monedas (¢)

      Más sobre el problema del cambio de monedas

      Problema del cambio de monedas

      Con unos pocos tipos de monedas, ¿cómo pagas una cantidad exacta con las menos monedas posibles, y de cuántas formas se puede hacer? La respuesta voraz, la moneda más grande primero, funciona con el dinero real, pero falla con algunos conjuntos de monedas. Una tabla que construye cada cantidad a partir de otras más pequeñas siempre acierta. Toca una moneda de la bandeja para ponerla en el mostrador, y toca una moneda del mostrador para retirarla. El medidor se llena hasta la cantidad: consíguela exacta, con las menos monedas que puedas. Mínimo de monedas muestra la mejor respuesta, y Voraz muestra lo que se obtiene tomando siempre la moneda más grande que cabe, que no siempre es el mínimo. Cambia las monedas (en céntimos) y la cantidad en el panel. La vista Tabla muestra cómo la programación dinámica encuentra el mínimo de monedas, o cuenta el número de formas de obtener la cantidad: pulsa Reproducir para ver cómo se llena la tabla, o Paso y Atrás para avanzar paso a paso, y arrastra el control de pasos para saltar a cualquier punto. Cada moneda se puede usar tantas veces como quieras. Con la tabla seleccionada, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

      Cómo funciona

      1. Toca monedas de la bandeja para formar exactamente la cantidad y mira cómo se llena el indicador en centavos.
      2. Intenta usar el menor número de monedas y luego pulsa Mínimo de monedas o Voraz para comparar.
      3. Abre la vista Tabla y pulsa Reproducir para ver cómo cada celda lee la cantidad menor de la que depende.

      Mínimo de monedas

      La cantidad 0 no necesita monedas. Para cada cantidad mayor, prueba cada moneda que no sea más grande que ella: lo que queda tras esa moneda es una cantidad menor, ya en la tabla, así que una moneda más da un candidato. El candidato más pequeño va a la celda, y la moneda que lo dio se guarda en la fila de abajo. Cuando la tabla está llena, las monedas se leen de vuelta desde el objetivo: toma su última moneda, ve a la cantidad que queda y repite hasta llegar a 0.

      Número de formas

      Para contar combinaciones en vez de órdenes, la tabla añade una moneda por fila. Una celda cuenta las formas de obtener su cantidad con las monedas hasta su fila: las formas sin la moneda más reciente, que es la celda de arriba, más las formas que usan la moneda más reciente al menos una vez, que es la celda tantas columnas a la izquierda en la misma fila. Como las monedas se añaden en un orden fijo, 1 + 2 y 2 + 1 son la misma forma y se cuentan una sola vez.

      Preguntas frecuentes

      ¿Por qué falla el método voraz?

      El algoritmo voraz siempre toma la moneda más grande que cabe y nunca se lo replantea. Con las monedas 1, 3 y 4 y una cantidad de 6, toma 4 y luego 1 y 1: tres monedas, cuando bastarían dos de 3. En sistemas de monedas como el euro o el dólar estadounidense, el voraz resulta ser óptimo; a estos sistemas se les llama canónicos.

      ¿Qué diferencia hay entre contar formas y contar órdenes?

      Las formas tratan 1 + 2 y 2 + 1 como la misma combinación; los órdenes los cuentan por separado. La aplicación cuenta formas, añadiendo las monedas fila a fila. Para contar órdenes, en cambio, se recorren las cantidades y se prueba cada moneda para cada una.

      ¿Cuánto tarda el algoritmo del cambio de monedas?

      Ambas tablas necesitan tantos pasos como el número de tipos de monedas por la cantidad. Es rápido para cantidades de miles, pero una cantidad puede ser un número enorme, así que, medido por su número de cifras, el problema es NP-difícil en general.

      ¿Y si una cantidad no se puede obtener?

      Su celda se queda en ∞, por ejemplo las cantidades 1 y 3 con las monedas 2 y 5. En el modo Número de formas, su recuento es simplemente 0.

      ¿Se envía algo a algún sitio?

      No. Todo se calcula en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.

      ¿Listo para probarlo?

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

      Ir al editor