python - 动态规划最优换币

Question

我一直在复习一些动态规划问题，我费了好大劲才想出一些代码来找到最少数量的硬币来找零。

假设我们有值(value) 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)(请原谅我的符号)。所以问题有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]