分而治之-最小变化-以数组形式返回硬币

Question

下面是最小硬币兑换问题的强力解决方案。它需要一个整数A（这是需要进行的更改）和一组硬币面额。它返回一个对象results，该对象具有基于硬币面额数组和硬币数组可以返回的最小硬币数。

例如，如果要求以[1,2,5]的值为10美分提供零钱，则它应返回2分钟硬币和两个一角硬币的数组[0,0,2]。

它返回正确的最小值，但不是正确的硬币数组。

# 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

这个问题最好通过使用动态规划来解决。例如，请参阅此http://www.columbia.edu/~cs2035/courses/csor4231。F07/动态。以下直观动态规划公式的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]