Problema de cambio de monedas

El problema de cambio de monedas aborda la forma de encontrar el número mínimo de monedas (de ciertas denominaciones) tales que entre ellas suman una cierta cantidad. Es un tipo de problema de la mochila, y tiene aplicaciones que exceden el ámbito específico de la circulación de dinero.

Ejemplo de solución al problema de dar cambio con modelos, si se utiliza un algoritmo voraz para determinar el mínimo número de monedas que debe devolverse en el cambio. En la figura se muestran los pasos que un ser humano debería seguir para emular a un algoritmo voraz para acumular 36 centavos usando sólo monedas de valores nominales de 1, 5, 10 y 20 centavos cada una. La moneda del mayor valor menor que el resto debido es el óptimo local en cada paso. Nótese que en general el problema de devolución del cambio requiere programación dinámica o programación lineal para encontrar una solución óptima. Sin embargo, muchos sistemas monetarios, incluyendo el euro y el dólar estadounidense, son casos especiales donde en la estrategia del algoritmo voraz da con la solución óptima.

Definición matemática

Los valores de las monedas se pueden representar mediante un conjunto de n valores enteros positivos distintos, ordenados en forma creciente desde w₁ = 1 hasta w_n.

El planteo del problema es: dada una cantidad W, que es un entero positivo, encontrar un conjunto de números enteros no negativos (positivos o cero) {x₁, x₂, ..., x_n}, donde cada incógnita x_j representa cuantas monedas de valor w_j se utilizan, de forma tal de minimizar el número total de monedas que se utilizan para sumar W

$\sum _{j=1}^{n}x_{j}$

sujeto a

$\sum _{j=1}^{n}w_{j}x_{j}=W.$

Ejemplo sin monedas

Una situación similar al problema de cambio, es por ejemplo encontrar las formas en que se puede hacer el lanzamiento de cierto número de dardos en un juego de dardos y obtener un puntaje W. Para este caso se tienen n valores distintos marcados en el tablero de forma tal que al lanzar cada dardo y atinar a un valor, estos valores se van sumando hasta llegar al puntaje objetivo W. El objetivo sería llegar a obtener el puntaje objetivo W con la mínima cantidad posible de lanzamientos.

Métodos de resolución

Programación dinámica sencilla

Una estrategia de resolución clásica de programación dinámica consistiría en encontrar en forma ascendente las combinaciones de todas las monedas de valores más pequeños cuya suma alcanza el umbral actual. Por lo tanto, en cada umbral, se considera potencialmente que todos los umbrales previos funcionan de forma ascendente para alcanzar la cantidad objetivo W. Por esta razón, este enfoque de programación dinámica puede requerir una cantidad de pasos que se incrementa en forma al menos cuadrática según sea el valor de la cantidad objetivo W.

Subestructura óptima

Como el problema presenta una subestructura óptima, se puede aplicar una estrategia de programación dinámica para encontrar una solución. El método es el siguiente:

Primero, dado que $S$ es la solución óptima que contiene exactamente $n$ monedas, por lo tanto $S'=S-c$. Puede parecer como si $c\in S$ fuese la solución óptima para el sub-problema que contiene exactamente $n-c$ monedas.

Sin embargo, $S'$ no contiene $n-c$ monedas y no es óptimo, por lo que la solución se conoce como $X\neq S'$, por lo tanto $X$ se convierte en la solución óptima, ya que debe contener menos cantidad de monedas que $S'$.

Finalmente, combinando $X$ con $c$ se obtiene la solución óptima que contiene exactamente $n$ monedas, lo que confirma que $S$ no era la solución óptima para el problema original.

Implementación

El siguiente algoritmo es una implementación de programación dinámica (con Python 3) que utiliza una matriz para realizar un seguimiento de las soluciones óptimas para sub-problemas y devuelve el número mínimo de monedas. Se puede usar una segunda matriz para obtener el conjunto de monedas para la solución óptima.

def _get_change_making_matrix(set_of_coins, r):
    m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]

    for i in range(r + 1):
        m[0][i] = i

    return m

def change_making(coins, n):
    """Esta función supone que todas las monedas están disponibles infinitamente.

    'n' es el número que se obtiene con el menor número de monedas.

    'coins' es una lista o tupla con las denominaciones disponibles."""

    m = _get_change_making_matrix(coins, n)

    for c in range(1, len(coins) + 1):

        for r in range(1, n + 1):

            # Solo utiliza una moneda coins[c - 1].
            if coins[c - 1] == r:
                m[c][r] = 1

            # coins[c - 1] no puede ser incluida.
            # Usa la solución anterior para hallar r,
            # excluyendo a coins[c - 1].
            elif coins[c - 1] > r:
                m[c][r] = m[c - 1][r]

            # coins[c - 1] se puede usar.
            # Decide cuál de las siguientes soluciones es la mejor:
            # 1. Usando la solución anterior para hallar r (sin usar coins[c - 1]).
            # 2. Usando la solución anterior para hallar r - coins[c - 1] (sin usar coins[c - 1]) más 1 de esta moneda.
            else:
                m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])

    return m[-1][-1]

Programación dinámica con el árbol de convolución probabilístico

Ejemplo: cálculo de $M_{(1,7,23)}(28)$ utilizando programación dinámica con el árbol de convolución probabilístico.

El árbol de convolución probabilístico​ también se puede usar 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 obtener con ese par de monedas (sin monedas presentes, solo la primera moneda presente, solo la segunda moneda presente y ambas monedas presentes), y luego fusionando pares de estos resultados combinados de la misma manera. Este proceso se repite hasta que las dos colecciones finales de resultados se combinan en una, lo que lleva a un árbol binario equilibrado con W log(W) operaciones de fusión. Además, al discretizar los valores de la moneda, cada una de estas operaciones de fusión se puede realizar a través de la 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ístico puede conseguir una solución en un sub-número cuadrático de pasos: cada convolución se puede realizar 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 más tardías (menos numerosas) requieren un n en el orden de W.

El método de programación dinámica basado en árboles de convolución probabilístico también resuelve eficientemente la generalización probabilística del problema de cambio de decisiones, donde la incertidumbre o la falta de claridad en la cantidad objetivo W hace que sea una distribución discreta en lugar de una cantidad fija, donde el valor de cada moneda es igualmente permitido ser borroso (por ejemplo, cuando se considera una tasa de cambio), y donde se pueden usar monedas diferentes con frecuencias particulares.

Método codicioso o voraz

En los denominados sistemas canónicos de monedas, tales como el que se usa en Estados Unidos, y en muchos otros países, se emplea un algoritmo codicioso o voraz. Según este algoritmo se elige la moneda de mayor denominación tal que no sea mayor que la cantidad restante para alcanzar el valor objetivo.​ Sin embargo, este algoritmo no es adecuado para los sistemas de monedas arbitrarios: si las denominaciones de las monedas fueran 1, 3 y 4, entonces para obtener 6, el algoritmo codicioso elegiría tres monedas (4,1,1) mientras que la solución óptima es dos monedas (3,3).

Problemas relacionados

El "problema de denominación óptima"​ es un problema que se adecúa a las personas que diseñan monedas completamente nuevas. En este problema se pregunta qué denominaciones se deben elegir para las monedas a fin de minimizar el costo promedio de hacer el cambio, es decir, el número promedio de monedas necesarias para hacer el cambio. La versión de este problema supone que las personas que hacen cambios usarán la cantidad mínima de monedas (de las denominaciones disponibles). Una variación de este problema supone que las personas que hacen cambios usarán el "algoritmo codicioso" para hacer cambios, incluso cuando eso requiera más que el número mínimo de monedas. La mayoría de las monedas actuales utilizan la serie 1-2-5, pero puede que algún otro conjunto de denominaciones requiera menos denominaciones de monedas o un número promedio menor de monedas para hacer cambios o ambos casos a la vez.

Véase también

• Problema de la mochila
• Problema de la moneda

Bibliografía

• X. Cai (2009). «Canonical Coin Systems for Change-Making Problems». Proceedings of the Ninth International Conference on Hybrid Intelligent Systems: 499-504. arXiv:0809.0400. doi:10.1109/HIS.2009.103. 
• M. Adamaszek, A. Niewiarowska (2010). «Combinatorics of the change-making problem». European Journal of Combinatorics 31 (1): 47-63. arXiv:0801.0120. doi:10.1016/j.ejc.2009.05.002. 

• Datos: Q3406279