El problema del cambio de moneda se ocupa de encontrar la cantidad mínima de monedas (de determinadas denominaciones) que suman una cantidad determinada de dinero. Es un caso especial del problema de la mochila con números enteros y tiene aplicaciones más amplias que el mero uso de la moneda.
Es también la variante más común del problema del cambio de monedas , un caso general de partición en el que, dadas las denominaciones disponibles de un conjunto infinito de monedas, el objetivo es averiguar el número de formas posibles de realizar un cambio para una cantidad específica de dinero, sin considerar el orden de las monedas.
Es débilmente NP-duro , pero puede resolverse de manera óptima en tiempo pseudopolinomial mediante programación dinámica . [1] [2]
Los valores de las monedas se pueden modelar mediante un conjunto de n valores enteros positivos distintos (números enteros), dispuestos en orden creciente desde w 1 hasta w n . El problema es: dada una cantidad W , también un entero positivo, encontrar un conjunto de enteros no negativos (positivos o cero) { x 1 , x 2 , ..., x n }, donde cada x j representa la frecuencia con la que se utiliza la moneda con valor w j , lo que minimiza el número total de monedas f ( W )
sujeto a
Una aplicación del problema del cambio se puede encontrar en el cálculo de las formas en que se puede lograr un final de nueve dardos en un juego de dardos.
Otra aplicación es calcular la posible composición atómica (o isotópica) de un pico de masa/carga dado en espectrometría de masas.
Una estrategia clásica de programación dinámica funciona de manera ascendente al encontrar las combinaciones de todos los valores más pequeños que sumarían el umbral actual. [3] Por lo tanto, en cada umbral, se considera que todos los umbrales anteriores funcionan potencialmente de manera ascendente hasta la cantidad objetivo W. Por esta razón, este enfoque de programación dinámica requiere una cantidad de pasos que es O( nW), donde n es la cantidad de tipos de monedas.
La siguiente es una implementación de programación dinámica (con Python 3) que utiliza una matriz para llevar un registro de las soluciones óptimas de los subproblemas y devuelve la cantidad mínima de monedas o "Infinito" si no hay forma de dar cambio con las monedas dadas. Se puede utilizar una segunda matriz para obtener el conjunto de monedas para la solución óptima.
def _get_change_making_matrix ( set_of_coins , r : int ): m = [[ 0 para _ en rango ( r + 1 )] para _ en rango ( len ( set_of_coins ) + 1 )] para i en rango ( 1 , r + 1 ): m [ 0 ][ i ] = float ( 'inf' ) # De manera predeterminada, no hay forma de hacer que el cambio devuelva mdef change_making ( coins , n : int ): """Esta función asume que todas las monedas están disponibles infinitamente. Si las monedas solo se van a usar una vez, cambia m[c][r - coin] a m[c - 1][r - coin]. n es el número a obtener con la menor cantidad de monedas. coins es una lista o tupla con las denominaciones disponibles. """ m = _get_change_making_matrix ( coins , n ) for c , coin in enumerate ( coins , 1 ): for r in range ( 1 , n + 1 ): # Solo usa la moneda si coin == r : m [ c ][ r ] = 1 # no se puede incluir la moneda. # Usa la solución anterior para hacer r, # excluyendo la moneda elif coin > r : m [ c ][ r ] = m [ c - 1 ][ r ] # se puede usar la moneda. # Decide cuál de las siguientes soluciones es la mejor: # 1. Usar la solución anterior para hacer r (sin usar monedas). # 2. Usar la solución anterior para hacer r - monedas (sin # usar monedas) más esta moneda extra. else : m [ c ][ r ] = min ( m [ c - 1 ][ r ], 1 + m [ c ][ r - monedas ]) return m [ - 1 ][ - 1 ] El árbol de convolución probabilístico [4] también se puede utilizar como un enfoque de programación dinámica más eficiente. El árbol de convolución probabilístico fusiona pares de monedas para producir todas las cantidades que se pueden crear con ese par de monedas (sin ninguna moneda presente, solo la primera moneda presente, solo la segunda moneda presente y ambas monedas presentes), y luego fusiona pares de estos resultados fusionados de la misma manera. Este proceso se repite hasta que las dos colecciones finales de resultados se fusionan en una, lo que conduce a un árbol binario equilibrado con W log(W) de tales operaciones de fusión. Además, al discretizar los valores de las monedas, cada una de estas operaciones de fusión se puede realizar mediante convolución, que a menudo se puede realizar de manera más eficiente con la transformada rápida de Fourier (FFT). De esta manera, el árbol de convolución probabilística puede utilizarse para lograr una solución en un número subcuadrático de pasos: cada convolución puede realizarse en n log(n) , y las operaciones de fusión iniciales (más numerosas) utilizan un n más pequeño , mientras que las operaciones posteriores (menos numerosas) requieren n en el orden de W .
El método de programación dinámica basado en árboles de convolución probabilística también resuelve de manera eficiente la generalización probabilística del problema de cambio, donde la incertidumbre o imprecisión en la cantidad objetivo W la convierte en una distribución discreta en lugar de una cantidad fija, donde también se permite que el valor de cada moneda sea difuso (por ejemplo, cuando se considera un tipo de cambio) y donde se pueden usar diferentes monedas con frecuencias particulares.
En muchos sistemas de monedas del mundo real, como los que se utilizan en los EE. UU. y en muchos otros países, un algoritmo codicioso que elija la denominación más grande de moneda que no sea mayor que la cantidad restante por fabricar producirá el resultado óptimo. Sin embargo, este no es el caso de los sistemas de monedas arbitrarios o incluso de algunos sistemas del mundo real. Por ejemplo, si consideramos las antiguas denominaciones de monedas indias (ahora retiradas) de 5, 10, 20 y 25 paise, entonces para fabricar 40 paise, el algoritmo codicioso elegiría tres monedas (25, 10, 5) mientras que la solución óptima es dos monedas (20, 20). Otro ejemplo es intentar fabricar 40 centavos de dólar estadounidense sin monedas de cinco centavos (denominación 25, 10, 1) con un resultado similar: el codicioso elige siete monedas (25, 10 y 5 × 1), pero la solución óptima es cuatro (4 × 10). Un sistema de monedas se denomina "canónico" si el algoritmo voraz siempre resuelve su problema de cambio de forma óptima. Es posible comprobar si un sistema de monedas es canónico en tiempo polinomial . [5]
El " problema de la denominación óptima" [6] es un problema para quienes diseñan monedas completamente nuevas. Pregunta qué denominaciones se deben elegir para las monedas con el fin de minimizar el costo promedio de dar cambio, es decir, el número promedio de monedas necesarias para dar cambio. La versión de este problema suponía que las personas que dan cambio utilizarían el número mínimo de monedas (de las denominaciones disponibles). Una variación de este problema supone que las personas que dan cambio utilizarían el "algoritmo codicioso" para dar cambio, incluso cuando eso requiere más que el número mínimo de monedas. La mayoría de las monedas actuales utilizan una serie 1-2-5 , pero algún otro conjunto de denominaciones requeriría menos denominaciones de monedas o un número promedio menor de monedas para dar cambio o ambas cosas.