Divide and Conquer - Minimum Change - Return Coins as Array

Question

Ниже приведена грубая сила решения проблемы с минимальной заменой монет. Требуется int A, который является внесенным изменением, и массив монетных деноминаций. Он возвращает объект, результаты, который имеет минимальные монеты, которые могут быть возвращены на основе массива монетных достоинств, а также массив монет.

Например, если просили дать сдачу на 10 центов со значениями [1, 2, 5], он должен вернуть 2 монеты мин и массив [0, 0, 2] для двух пятаков.

Он возвращает правильное значение min, но не правильный массив монет.

# values the algorithms should return, the min num of coins, the actual  
# coins in an array, and the original 

# array of coin denominations 
class Results: 

    a = 0 
    change = [] 
    coinsDenom = [] 

# A is an array of coin denominations 
# C is the change to be made 
# returns results object 
def changeslow(A, C): 
    res = Results() 
    res.coinsDenom = C 
    res.change = [] 
    # initialize your change array to be the length of the coindenom array 
    for i in range(0, len(res.coinsDenom)): 
     res.change.append(0) 

    minCoins = A 

    for i in [j for j in C if j <= A]: 
     if j == A: 
      res.a = 1 
      res.change[i] = res.change[i] + 1 
      return res 

     nextcall = changeslow(A-i, C) 
     numCoins = 1 + nextcall.a 

     if numCoins < minCoins: 
      minCoins = numCoins 
      res.change = nextcall.change 
      res.change[0] = res.change[0] + 1 



    res.a = minCoins 

    return res 

Answer 1

Эта проблема лучше всего решить, используя dynamic programming. Например, обратитесь к этому http://www.columbia.edu/~cs2035/courses/csor4231.F07/dynamic.pdf для следующей интуитивной формулировки динамического программирования:

# DP-CHANGE 
# find number of coins needed to represent a value and memoize the last coin 
def DP_CHANGE(denoms, value): 
    num_coins = [0]*(value+1) # store number of coins needed to represent coin values from [0..value] 
    last_coin = [float('Inf')]*(value+1) # memoize last coin used to represent coin values from [0..value] 
    for d in denoms: 
     num_coins[d] = 1 
    for i in range(1, value + 1): 
     num_denom = min([(num_coins[i-d] + 1, d) for d in denoms if i - d >= 0]) 
     num_coins[i], last_coin[i] = num_denom[0], num_denom[1] 
    return num_coins, last_coin 

# TRACE-CHANGE 
# back-trace the denominations used 
def TRACE_CHANGE(value, last_coin): 
    denoms_used = [] 
    while value > 0: 
     denoms_used.append(last_coin[value]); 
     value-=last_coin[value] 
    return denoms_used 

def FIND_CHANGE(value, denoms): 
    num_coins, last_coin = DP_CHANGE(denoms, value) 
    print 'number of coins needed to represent values ' + str(range(value+1)) + ': ' + str(num_coins) 
    print 'minimum number of coins need to represent the value ' + str(value) + ': ' + str(num_coins[value]) 
    print 'coins of denominations needed:' + str(TRACE_CHANGE(value, last_coin)) 

FIND_CHANGE(10, [1,2,5]) 
# number of coins needed to represent values [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]: 
#           [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2] 
# minimum number of coins need to represent the value 10: 2 
# coins of denominations needed:[5, 5]