动态规划优化硬币变化

我一直在评论一些动态编程问题，而且我很难在寻找最小数量的硬币来进行更改时绕过一些代码。假设我们有价值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号线是我开始感到困惑），这将是巨大的。谢谢！

来源

2012-12-06 tect

什么是'minCoins'？无论如何，试图解决这个问题一般相当于背包问题（或者甚至更糟糕），所以在任何情况下寻找最佳解决方案都会非常快速地产生麻烦。解决方案可能取决于您可以使用的硬币。 – Bakuriu

在[l for list_comprehension]中为变量写''变量在主观上是不好的，仅仅因为我没有看到太多... – Droogans

它很尴尬，但并不真的太可怕。这只是缩小了名单。同样的事情可以通过下一行中的“if”和“continue”来完成，但是无论如何。 – acjay

在我看来，代码正在解决每个分值的问题，直到目标分值为止。鉴于目标值v和一组硬币C的，你知道的最佳选择硬币有S是形式union(S', c)，其中c为C和S'一些硬币是v - value(c)最优解（原谅我的符号）的。所以这个问题有optimal substructure。动态规划方法是解决每个可能的子问题。这需要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-07 01:43:46 acjay

不错，很清楚。基本上，我们知道用来做“改变”的硬币收集必须包括（a）coinValueList中的一些硬币加上（b）一堆其他硬币用于组成剩余硬币。因此，为（a）“猜出”一枚硬币，然后查找改变余地的最佳方法。（方便的是，其余的比'变化'更小，所以我们必须在早期的循环迭代中找到最佳解决方案。）如果我们对（a）（即每个不同的硬币值）的每个可能的猜测重复这一点，则（至少）这些（a）中的一个加上其相应的（b）必须是最优的。 –

谢谢！这很简单，很好解释，我现在明白这个问题是如何工作的。 – tect

太棒了！如果你全部设置，请随时打勾选接受答案:) – acjay

我认为第四行是混乱的，因为虽然Python可以在列表理解(transform(x) for x in iterable if condition(x))选择/过滤器，它不能做同样在其标准for x in iterable:表达。

所以一个人（cheesy 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-07 01:53:49

这里是一个办法考虑一下可能有用的硬币改变问题，如果你对图理论感到满意的话。

假设你有下列方式定义的图形：

有一个节点的钱每个单位从0（例如，便士）到你感兴趣的（例如，39美分的价值，或其他）。
在任何两个节点之间有一条弧，这两个节点之间用一个允许使用的硬币的值完全分开（例如，如果允许使用镍，则节点在34美分到29美分之间）。

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

该算法不使用图论的术语，但它做的事情基本上是一样的：外层循环覆盖所有“美分”（或在图论框架中的节点），内层循环是范围从当前弧线到下一弧线的所有弧线（coinValueList中的值）。总而言之，他们正在寻找从零到您感兴趣的价值的最短路径。（数值降到零，零到达数值并不重要，传统上我们搜索到的数值为零）

我只有真正开始理解动态规划，当我意识到许多问题可能会转化为图形问题。（但要小心 - 不是所有的都可以，有些是超图，有些甚至可能不是，但它对我有很大的帮助。）

来源

2012-12-08 20:43:24 Novak

动态规划优化硬币变化

回答

相关问题