动态规划最优硬币找零 [英] Dynamic Programming Optimal Coin Change

问题描述

我一直在检讨一些动态规划的问题，和我有很难包装我的头周围的一些code的问候寻找最小的硬币数量做出改变。

I've been reviewing some dynamic programming problems, and I have had hard time wrapping my head around some code in regards to finding the smallest number of coins to make change.

假设我们有硬币价值25，10，1，我们正在变化30.贪婪将回到25和第5（1），而最佳的解决方案将返回3（10）。下面是这本书在这个问题上的code：

Say we have coins worth 25, 10, and 1, and we are making change for 30. Greedy would return 25 and 5(1) while the optimal solution would return 3(10). Here is the code from the book on this problem:

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]

如果有人可以帮助我环绕这个code我的头（4号线是我开始感到困惑），这将是巨大的。谢谢！

If anyone could help me wrap my head around this code (line 4 is where I start to get confused), that would be great. Thanks!

推荐答案

在我看来像code为求解每一分钱的价值，直到目标美分值的问题。给定一个目标值 v 和一组硬币 C ，你知道最佳的硬币选择取值必须是形式工会（S'，C），其中 C 是 C语言带来的硬币和 S'是诉最佳解决方案 - 值（ C）（原谅我的符号）。所以，问题有最优子。动态规划方法是解决一切可能的子问题。它采用仙*尺寸（C）的步骤，而不是东西，更迅速，如果你只是尝试暴力破解直接的解决方案吹了起来。

It looks to me like the code is solving the problem for every cent value up until target cent value. Given a target value v and a set of coins C, you know that the optimal coin selection S has to be of the form union(S', c), where c is some coin from C and S' is the optimal solution for v - value(c) (excuse my notation). So the problem has optimal substructure. The dynamic programming approach is to solve every possible subproblem. It takes cents * size(C) steps, as opposed to something that blows up much more quickly if you just try to brute force the direct solution.

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]

这篇关于动态规划最优硬币找零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！