Programación dinámica simpleEditar
Una estrategia clásica de programación dinámica funciona hacia arriba encontrando las combinaciones de todos los valores más pequeños que sumarían al umbral actual. Así, en cada umbral, todos los umbrales anteriores se consideran potencialmente para trabajar hacia arriba hasta la cantidad objetivo W. Por esta razón, este enfoque de programación dinámica requiere un número de pasos que es O(nW), donde n es el número de tipos de monedas.
ImplementaciónEditar
La siguiente es una implementación de programación dinámica (con Python 3) que utiliza una matriz para llevar la cuenta de las soluciones óptimas a los subproblemas, y devuelve el número mínimo de monedas, o «Infinito» si no hay manera de hacer el 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 = for _ in range(len(set_of_coins) + 1)] for i in range(1, r + 1): m = float('inf') # By default there is no way of making change return mdef change_making(coins, n: int): """This function assumes that all coins are available infinitely. n is the number to obtain with the fewest coins. coins is a list or tuple with the available denominations. """ m = _get_change_making_matrix(coins, n) for c in range(1, len(coins) + 1): for r in range(1, n + 1): # Just use the coin coins. if coins == r: m = 1 # coins cannot be included. # Use the previous solution for making r, # excluding coins. elif coins > r: m = m # coins can be used. # Decide which one of the following solutions is the best: # 1. Using the previous solution for making r (without using coins). # 2. Using the previous solution for making r - coins (without # using coins) plus this 1 extra coin. else: m = min(m, 1 + m]) return m
Programación dinámica con el árbol de convolución probabilísticoEditar
El árbol de convolución probabilístico también se puede utilizar como un enfoque de programación dinámica más eficiente. El árbol de convolución probabilística fusiona pares de monedas para producir todas las cantidades que pueden ser creadas por ese par de monedas (con ninguna moneda presente, sólo la primera moneda presente, sólo la segunda moneda presente, y ambas monedas presentes), y luego posteriormente fusiona pares de estos resultados fusionados de la misma manera. Este proceso se repite hasta que las dos últimas colecciones de resultados se fusionan en una, lo que da lugar a un árbol binario equilibrado con W log(W) operaciones de fusión de este tipo. Además, al discretizar los valores de las monedas, cada una de estas operaciones de fusión puede realizarse mediante una convolución, que a menudo puede llevarse a cabo de forma más eficiente con la transformada rápida de Fourier (FFT). De este modo, el árbol de convolución probabilístico 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 del orden de W.
El método de programación dinámica basado en el árbol de convolución probabilístico también resuelve eficientemente la generalización probabilística del problema de la realización de cambios, donde la incertidumbre o la vaguedad de la cantidad objetivo W la convierte en una distribución discreta en lugar de una cantidad fija, donde se permite que el valor de cada moneda sea igualmente difuso (por ejemplo, cuando se considera un tipo de cambio), y donde se pueden utilizar diferentes monedas con frecuencias particulares.
Método codiciosoEditar
Para los llamados sistemas de monedas canónicas, como los utilizados en los EE.UU. y muchos otros países, un algoritmo codicioso de escoger la mayor denominación de moneda que no sea mayor que la cantidad restante a realizar producirá el resultado óptimo. Sin embargo, este no es el caso de los sistemas de monedas arbitrarios. Por ejemplo, si las denominaciones de las monedas fueran 1, 3 y 4, para hacer 6, el algoritmo codicioso elegiría tres monedas (4,1,1), mientras que la solución óptima son dos monedas (3,3). Es posible comprobar si un sistema de monedas es canónico (es decir, si el algoritmo codicioso siempre resuelve su problema de cambio de forma óptima) en tiempo polinómico.