18

我正在寻找一个很好的解决方案来解决变革问题，我发现了这段代码（Python）：

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

我理解代码的字面意思没有问题，但我不明白它为什么起作用。任何人都可以帮忙吗？

4

4 回答 4

16

要获得元素等于“a”或“b”或“c”（我们的硬币）且总和为“X”的所有可能集合，您可以：

  • 取所有这样的集合，总和为 Xa，并为每个集合添加一个额外的“a”。
  • 取所有这些总和为 Xb 的集合，并为每个集合添加一个额外的“b”。
  • 取所有这些总和为 Xc 的集合，并为每个集合添加一个额外的“c”。

所以你能得到 X 的方法数是你能得到 Xa 和 Xb 和 Xc 的方法数之和。

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

休息是简单的复发。

额外提示：一开始你可以用一种方式设置总和为零（空集）

ways = [1]+[0]*target
于 2013-02-21T01:19:24.470 回答
10

这是动态规划的经典例子。它使用缓存来避免像 3+2 = 5 这样计算两次的陷阱（因为另一种可能的解决方案：2+3）。递归算法落入了这个陷阱。让我们关注一个简​​单的例子， wheretarget = 5和coins = [1,2,3]. 您发布的代码很重要：

  1. 3+2
  2. 3+1+1
  3. 2+2+1
  4. 1+2+1+1
  5. 1+1+1+1+1

而递归版本很重要：

  1. 3+2
  2. 2+3
  3. 3+1+1
  4. 1+3+1
  5. 1+1+3
  6. 2+1+2
  7. 1+1+2
  8. 2+2+1
  9. 2+1+1+1
  10. 1+2+1+1
  11. 1+1+2+1
  12. 1+1+1+2
  13. 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-21T01:38:10.813 回答
4

代码背后的主要思想如下：“在每一步都有ways办法改变i给定硬币的金额[1,...coin]”。

因此，在第一次迭代中，您只有一枚面额为 的硬币1。我相信很明显，只有一种方法可以让任何目标都只使用这些硬币。在这一步上，ways数组看起来像（从to[1,...1]的所有目标只有一种方式）。0target

在下一步中，我们将面额为 的硬币添加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]。

上面给出的代码完全等同于递归解决方案。如果您了解递归解决方案，我敢打赌您了解上面给出的解决方案。

于 2013-02-21T01:39:02.780 回答
-1

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

    /// <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-12T22:12:48.003 回答