Problema de cambio de monedas

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.

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 ${\displaystyle S}$ es la solución óptima que contiene exactamente ${\displaystyle n}$ monedas, por lo tanto ${\displaystyle S'=S-c}$. Puede parecer como si ${\displaystyle c\in S}$ fuese la solución óptima para el sub-problema que contiene exactamente ${\displaystyle n-c}$ monedas.

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

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

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]

Ejemplo: cálculo de ${\displaystyle 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[1] 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.

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.[2] 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).