algorithm - 硬币变化，动态规划，但硬币值(value)在第一次使用后减少

Question

周围有很多硬币找零问题和答案，但我找不到这个，我想知道这是否是一个硬币找零问题。

基本上我有一堆不同的硬币，每个硬币的数量都是无限的。

假设有一堆不同的面额。每个堆栈是无限的。 (无限数量的 25c 硬币，无限数量的 2c 硬币等)。

然而，在每一堆硬币的顶部都有一枚特殊的硬币，其值(value)大于(或等于)下面的硬币。如果不使用顶部的硬币，我将无法访问下面的硬币。

我要计算的是达到一定金额所需的最少硬币数量。

我认为这是可解决的动态规划，但我不确定如何将此限制添加到传统解决方案中。

我想知道我是否应该在我使用特殊硬币后将其从我的列表中删除并用普通硬币替换它，但我似乎无法推断这是否会破坏算法。

Answer 1

看起来像一个经典的动态规划问题，其中的挑战是正确选择状态。

通常，我们选择所选硬币的总和作为问题状态，并选择所选硬币的数量作为状态值。过渡是我们可以采用的每一种可能的硬币。如果我们有 25c 和 5c 硬币，我们可以从值为 Count 的状态 Sum 移动到状态 Sum+25,count+1 和 Sum+5,count+1。

对于您的限制，应该使用有关哪些特殊(顶级)硬币被拿走的信息来扩充状态。所以你为每一叠硬币加一点。然后你只需要定义每个状态的可能转换。很简单:如果设置了一个堆栈位，这意味着顶部硬币已经被拿走，你可以从那个堆栈中添加一个非顶部硬币到状态总和，保持所有位相同。否则，您可以从该堆栈中取出顶部硬币，将其值添加到状态总和，并设置相关位。

您从总和为 0 的状态开始，所有位都清零且值为 0，然后从最低总和到目标构建状态。

最后，您应该遍历位和的所有可能组合。将状态值与目标总和和该位组合进行比较。选择最小值 - 这就是答案。

示例解决方案代码:

#Available coins: (top coin value, other coins value)
stacks = [(17,8),(5,3),(11,1),(6,4)]
#Target sum
target_value = 70

states = dict()
states[(0,0)] = (0,None,None)
#DP going from sum 0 to target sum, bottom up:
for value in xrange(0, target_value):
    #For each sum, consider every possible combination of bits
    for bits in xrange(0, 2 ** len(stacks)):
        #Can we get to this sum with this bits?
        if (value,bits) in states:
            count = states[(value,bits)][0]
            #Let's take coin from each stack
            for stack in xrange(0, len(stacks)):                
                stack_bit = (1 << stack)                
                if bits & stack_bit:
                    #Top coin already used, take second
                    cost = stacks[stack][1]
                    transition = (value + cost, bits)
                else:
                    #Top coin not yet used
                    cost = stacks[stack][0]
                    transition = (value + cost, bits | stack_bit)
                #If we can get a better solution for state with sum and bits
                #update it 
                if (not (transition in states)) or states[transition][0] > count + 1:
                    #First element is coins number
                    #Second is 'backtrack reference'
                    #Third is coin value for this step
                    states[transition] = (count+1, (value,bits), cost)

min_count = target_value + 1
min_state = None
#Find the best solution over all states with sum=target_value
for bits in xrange(0, 2 ** len(stacks)):
    if (target_value,bits) in states:
        count = states[(target_value,bits)][0]
        if count < min_count:
            min_count = count
            min_state = (target_value, bits)
collected_coins = []
state = min_state
if state == None:
    print "No solution"
else:
    #Follow backtrack references to get individual coins
    while state <> (0,0):
        collected_coins.append(states[state][2])
        state = states[state][1]
    print "Solution: %s" % list(reversed(collected_coins))