硬币变化，动态规划，但硬币价值在第一次使用后减少

Question

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

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

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

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

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

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

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

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))

Answer 2

以下解决方案基于两个事实 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]

硬币变化，动态规划，但硬币价值在第一次使用后减少

Coin change, dynamic programming, but coin value reduces after first use

algorithm

dynamic-programming

knapsack-problem

coin-change