硬币更换，动态规划，但首次使用后硬币价值降低

Question

有很多关于硬币兑换的问题和答案，但我找不到这一个，我想知道这是否是一个硬币兑换的问题。

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

比如说有很多不同的面额。每个堆栈都是无限的。（因此，25摄氏度硬币的数量是无限的，2摄氏度硬币的数量是无限的，等等）。

然而，在每一堆硬币的顶部是一种特殊的硬币，其价值大于（或等于）下面的硬币。如果不在上面使用这枚硬币，我就无法访问下面的硬币。

我试图计算出的是获得一定金额所需的最低硬币数量。

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

我在想，一旦我使用了特殊硬币，我是否应该在我的列表中删除它，并用普通硬币替换它，但我似乎无法判断这是否会破坏算法。

Answer 1

下面的解决方案基于两个事实1）无限数量的硬币在所有可用的面额

Algorithm:-

Let Given number be x

call the below method repeatedly until you reach your coin value, 
Each time of iteration pass the remaining value to be assigned with coins    and also the coin denomination

Method which will receive the number and the coin value
Parameters: x - coin to be allocated
            z - value of coin
if(x > z) {
   integer y = x/z * z
   if(y == x) {
      x is divisible by z and hence allocate with x/z number of coins of z value.
 }  
   if(Y != x) {
       x is not a multiple of z and hence allocate with x/z number of coins from z cents value and then for remaining amount repeat the same logic mentioned here by having the next greatest denomination of
  coin.

   }
 }
 else if(x < z) {
     return from this method;
 }
 else if(x == z) {
     x is divisible by z and hence allocate with x/z number of coins of z value    
 }


Example iteration:

Given number = 48c
Coins denomination: 25c, 10c, 5c, 2c, 1c

First Iteration:

Parameter x = 48c and z = 25c
return value would be a map of 1 coin of 25c, [25c , 1]
calculate the remaining amount 48c - 25c = 23c
23c is not equal to zero and not equal to 1 continue the loop.

Second Iteration:

Parameter x = 23c and z = 10c
return value would be a map of 2 coins of 10c, [10c, 2]
calculate the remaining amount 23c - 20c = 3c
3c is not equal to zero and not equal to 1 continue the loop.

Third Iteration:

Parameter x = 3c and z = 5c
No coins allocated
3c is not equal to zero and not equal to 1 continue the loop.

Fourth Iteration:

Parameter x = 3c and z = 2c
return value would be a map of 1 coin of 2c, [2c, 1]
Remaining amount 3c - 2c = 1c
Remaining amount Equals to 1 add an entry in map [1c, 1]


Final Map Entries:

[25c, 1]
[10c, 2]
[2c, 1]
[1c, 1]
[1c, 1]

Answer 2

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

通常，我们选择所选硬币的总数作为问题状态，选择所选硬币的数量作为状态值。过渡是我们能得到的一切可能的硬币。如果我们有25c和5c硬币，我们可以从有值计数的状态总和转移到状态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))