Algoritmo de cambio de monedas

Question

Supongamos que tengo un juego de monedas con las denominaciones a1, a2, ... ak.

Uno de ellos es conocido por ser igual a 1.

Quiero hacer el cambio para todos los enteros 1 a N utilizando el número mínimo de monedas.

Cualquier idea para el algoritmo.

eg. 1, 3, 4 coin denominations 
n = 11 
optimal selection is 3, 0, 2 in the order of coin denominations. 

n = 12 
optimal selection is 2, 2, 1. 

Nota: No tarea sólo una modificación de this problema

Answer 1

Se trata de un problema de programación dinámica clásica (tenga en cuenta que el primer algoritmo voraz no siempre funciona aquí!).

Suponga que las monedas están ordenadas de modo que a_1 > a_2 > ... > a_k = 1. Definimos un nuevo problema. Decimos que el problema (i, j) es encontrar el número mínimo de monedas que hacen el cambio para j usando monedas a_i > a_(i + 1) > ... > a_k. El problema que deseamos resolver es (1, j) para cualquier j con 1 <= j <= n. Supongamos que C(i, j) es la respuesta al problema (i, j).

Ahora, considere una instancia (i, j). Tenemos que decidir si estamos usando o no una de las monedas a_i. Si no lo estamos, solo estamos resolviendo un problema (i + 1, j) y la respuesta es C(i + 1, j). Si lo estamos, completamos la solución haciendo cambios para j - a_i. Para hacer esto usando la menor cantidad de monedas posible, queremos resolver el problema (i, j - a_i). Arreglamos las cosas para que estos dos problemas ya están resueltos por nosotros y luego:

C(i, j) = C(i + 1, j)       if a_i > j 
     = min(C(i + 1, j), 1 + C(i, j - a_i)) if a_i <= j 

Ahora averiguar lo que los casos iniciales son y cómo se traduce esto en el idioma de su elección y usted debe ser bueno para ir.

Si quiere probar sus manos en otro problema interesante que requiere programación dinámica, mire el Proyecto Euler Problem 67.

Answer 2

Aquí hay una implementación de ejemplo de un algoritmo de programación dinámica en Python. Es más simple que el algoritmo que describe Jason, porque solo calcula 1 fila de la tabla 2D que describe.

Tenga en cuenta que el uso de este código para hacer trampa en la tarea hará llorar a Zombie Dijkstra.

import sys 
def get_best_coins(coins, target): 
    costs = [0] 
    coins_used = [None] 
    for i in range(1,target + 1): 
     if i % 1000 == 0: 
      print '...', 
     bestCost = sys.maxint 
     bestCoin = -1 
     for coin in coins: 
      if coin <= i: 
       cost = 1 + costs[i - coin] 
       if cost < bestCost: 
        bestCost = cost 
        bestCoin = coin 
     costs.append(bestCost) 
     coins_used.append(bestCoin) 
    ret = []  
    while target > 0: 
     ret.append(coins_used[target]) 
     target -= coins_used[target] 
    return ret 

coins = [1,10,25] 
target = 100033 
print get_best_coins(coins, target)