7

我一直在审查一些动态编程问题，并且我很难围绕一些代码来寻找最少数量的硬币来进行更改。

假设我们有价值 25、10 和 1 的硬币，我们正在找零 30。贪婪将返回 25 和 5(1)，而最优解将返回 3(10)。这是书中关于这个问题的代码：

def dpMakeChange(coinValueList,change,minCoins):
   for cents in range(change+1):
      coinCount = cents
      for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1
      minCoins[cents] = coinCount
   return minCoins[change]

如果有人能帮助我理解这段代码（第 4 行是我开始感到困惑的地方），那就太好了。谢谢！

4

3 回答 3

5

在我看来，代码正在解决每个美分值的问题，直到目标美分值。给定一个目标值v和一组硬币C，您知道最佳硬币选择S必须是形式union(S', c)，其中c一些硬币来自哪里，C并且S'是最佳解决方案v - value(c)（请原谅我的符号）。所以问题有最优子结构。动态规划方法是解决所有可能的子问题。它需要cents * size(C)一些步骤，而不是如果你只是试图暴力破解直接解决方案，那么事情就会爆炸得更快。

def dpMakeChange(coinValueList,change,minCoins):
   # Solve the problem for each number of cents less than the target
   for cents in range(change+1):

      # At worst, it takes all pennies, so make that the base solution
      coinCount = cents

      # Try all coin values less than the current number of cents
      for j in [c for c in coinValueList if c <= cents]:

            # See if a solution to current number of cents minus the value
            # of the current coin, with one more coin added is the best 
            # solution so far  
            if minCoins[cents-j] + 1 < coinCount:
               coinCount = minCoins[cents-j]+1

      # Memoize the solution for the current number of cents
      minCoins[cents] = coinCount

   # By the time we're here, we've built the solution to the overall problem, 
   # so return it
   return minCoins[change]
于 2012-12-07T01:43:46.327 回答
4

如果您对图论感到满意，这里有一种思考硬币兑换问题的方法可能有用。

假设您有一个按以下方式定义的图形：

  • 从 0 到您感兴趣的值（例如 39 美分或其他）的每个货币单位（例如便士）都有一个节点。
  • 任意两个节点之间有一条弧线，由您允许使用的硬币的价值隔开（例如，如果允许您使用镍币，则在 34 美分和 29 美分之间的节点。）

现在您可以将硬币更换问题视为从您感兴趣的值下降到零的最短路径问题，因为硬币的数量将与您路径中的弧数完全相同。

该算法不使用图论术语，但它做的事情基本相同：外循环覆盖所有“分”（或节点，在图论框架中），内循环覆盖所有从当前弧到下一个弧的弧（coinValueList 中的值）。总之，他们正在寻找从零到您感兴趣的价值的最短路径。（值降到零，零到值，无关紧要。不过，传统上我们向下搜索到零。）

当我意识到许多问题可以转换为图问题时，我才真正开始理解动态编程。（不过要小心——不是所有的都可以。有些是超图，有些可能甚至不是。但它对我帮助很大。）

于 2012-12-08T20:43:24.473 回答
3

我认为第四行令人困惑，因为虽然 Python 可以在列表理解中选择/过滤(transform(x) for x in iterable if condition(x))，但它不能在其标准for x in iterable:表达式中做同样的事情。

因此，人们绕过的一种（俗气的imo）方法是将两者焊接在一起。他们创建了一个实际上不进行转换的列表理解（因此是c for c in coinValueList），因此他们可以添加if c <= cents子句。然后将其用作标准for x in iterable:表达式的可迭代对象。我怀疑这就是你的一些困惑的来源。

编写该行的另一种方法可能是：

...
for eachCoinValue in filter(lambda x: x <= cents, coinValueList):
...

或者更清楚地说，“意图揭示变量”将是：

...
smallEnoughCoins = filter(lambda each: each <= cents)
for each in smallEnoughCoins:
    ...
于 2012-12-07T01:53:49.283 回答