动态规划最优硬币变化

Question

我一直在审查一些动态编程问题,而且我很难绕过一些代码来寻找最小数量的硬币来进行更改.

假设我们有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行是我开始感到困惑的地方),那就太好了.谢谢!

Answer 1

在我看来,代码正在解决问题,每一分钱值直到目标分值.给定目标值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]