理解变革的决策算法

我一直在寻找一个很好的解决了Change-making problem我发现这个代码（蟒蛇）：理解变革的决策算法

target = 200 
coins = [1,2,5,10,20,50,100,200] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin,target+1): 
     ways[i]+=ways[i-coin] 
print(ways[target])

我的理解没有问题了代码字面上做，但我不能理解它为什么有效。任何人都可以提供帮助吗？

来源

2013-02-21 gyosko

要获得所有可能的集合的元素等于“A”或“B”或“C”（我们的硬币），总计为“X”，你可以：

采取所有集，总结到Xa并为每一个添加一个额外的'a'。
把所有这些总和为X-b的组合加到每一个上并加上一个额外的'b'。
把所有这些总和为X-c的组合加到每一个上并加上一个额外的'c'。

所以你可以得到X的方法的数量是你可以得到X-a和X-b和X-c的方法总数。

ways[i]+=ways[i-coin]

休息是简单的重复。

额外提示：在开始时，你可以在只有一个方式（空集）

ways = [1]+[0]*target

来源

2013-02-21 01:19:24 fsw

这是一个dynamic programming经典的例子得到设定总和为零。它使用缓存来避免计数诸如 3 + 2 = 5两次（因为另一个可能的解决方案：2 + 3）的错误。递归算法陷入这个陷阱。我们来看一个简单的例子，其中target = 5和coins = [1,2,3]。的代码段你贴计数：

3 + 2
3 + 1 + 1
2 + 2 + 1
1 + 2 + 1 + 1
1 + 1 + 1 + 1个+ 1

而递归版本计数：

3 + 2
2 + 3
3 + 1 + 1
1 + 3 + 1
1 + 1 + 3
2 + 1 + 2
1 + 1 + 2
2 + 2 + 1
2 + 1 + 1 + 1
1 + 2 + 1 + 1
1 + 1 + 2 + 1
1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1

递归代码：

coinsOptions = [1, 2, 3] 
def numberOfWays(target): 
    if (target < 0): 
     return 0 
    elif(target == 0): 
     return 1 
    else: 
     return sum([numberOfWays(target - coin) for coin in coinsOptions]) 
print numberOfWays(5)

动态规划：

target = 5 
coins = [1,2,3] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin, target+1): 
     ways[i]+=ways[i-coin] 
print ways[target]

来源

2013-02-21 01:38:10

代码背后的主要思想是： “在每个步骤中有ways方法来改变i金额给予硬币[1,...coin]“。

因此，在第一次迭代中，您只有面额为1的硬币。我相信显而易见的是，只有一种方法可以让任何目标只有这些硬币。在此步骤ways阵列将看起来像[1,...1]（从0到target的所有目标只有一种方法）。

在下一步我们添加面额为2的硬币到上一组硬币。现在我们可以计算出0到target之间每个目标的变化组合数量。显然，组合的数量只会增加> = 2（或一般情况下添加新硬币）。因此，对于目标等于2的组合数将为ways[2](old) + ways[0](new)。一般来说，每当i等于推出新硬币时，我们需要将1添加到之前的组合数，其中新组合将仅由一枚硬币组成。

对于target>2，答案将包括“具有的target量的所有组合都小于coin硬币”和“coin量的所有组合具有比coin本身少所有硬币”的总和。

这里我描述了两个基本步骤，但我希望能够很容易地推广它。

让我告诉你target = 4和coins=[1,2]的计算树：

方法[4]给出币= [1,2] =

方法[4]给出币= [1] +方法[2]给出的硬币= [1,2] =

1 +方式[2]给出的硬币= [1] +方法[0]给定硬币= [1,2] =

1 + 1 + 1 = 3

所以有三种方法可以进行更改：[1,1,1,1], [1,1,2], [2,2]。

上面给出的代码完全等价于递归解决方案。如果您了解the recursive solution，我敢打赌你明白上面给出的解决方案。

来源

2013-02-21 01:39:02

您发布的解决方案是此代码的摘要版本。

/// <summary> 
    /// We are going to fill the biggest coins one by one. 
    /// </summary> 
    /// <param name="n"> the amount of money </param> 
    public static void MakeChange (int n) 
    { 
     int n1, n2, n3; // residual of amount after each coin 
     int quarter, dime, nickel; // These are number of 25c, 10c, 5c, 1c 
     for (quarter = n/25; quarter >= 0; quarter--) 
     { 
      n1 = n - 25 * quarter; 
      for (dime = n1/10; dime >= 0; dime--) 
      { 
       n2 = n1 - 10 * dime; 
       for (nickel = n2/5; nickel >= 0 && (n2 - 5*nickel) >= 0; nickel--) 
       { 
        n3 = n2 - 5 * nickel; 
        Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, n3); // n3 becomes the number of cent. 
       } 
      } 
     } 
    }

来源

2017-04-12 22:12:48 Aaron

理解变革的决策算法

回答

相关问题