优化变更解决方案

Question

我在这里编写了一个Python解决方案，它解决了以下问题：如何用最少数量的给定面额的硬币来制造给定数量的货币？

def min_coin_change(n, d):
    mini = float("inf")
    for den in d:
        diff = n - den
        if diff == 0:
            ans = 1
        elif diff < 0:
            ans = float("inf")
        else:
            ans = 1 + min_coin_change(n - den, d)
        mini = min(mini, ans)
    return mini

虽然我的解决方案有效，但当n大于50或d的长度大于5时，需要很长时间。我怎样才能加快代码的速度，使其能够在相当大的输入下工作？我是否错过了一个技巧或其他可以大大加快代码速度的东西？

Answer 1

这是因为它是递归的

阅读这个什么是记忆化，我如何在Python中使用它？（和前两个答案）

“记忆化”会记住你已经计算过的东西（比如10美分），这样你就不会以指数级的次数重新计算它们。

您可以按原样复制Mwmoize类，只需“装饰”您的函数，如第二个答案中所述

懒人

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        return self.memo[args]

然后在定义前添加装饰器

@Memoize
def min_coin_change(n,d)......

函数的其余部分是相同的

那你叫它

min_coin_change(30,(25,10,5,1))

Answer 2

请注意，您应该将函数设置为从最大的硬币开始，循环查找最大可能数量的最大硬币，然后重复下一个最大的硬币。

因此，den应按降序排序

def changecoin(d, denval)
  count = 0
  while d > denval:
    d -= denval
    count += 1
  return count, d

现在调用具有下一个最低值denval和新值d的递归，并适当地增加计数。

newcount = 0
for denval in den:
    count, d = changecoin(d, denval)
    newcount += count

实际上，在代码中，可以通过省略而在某种程度上修复Changecoin函数，这样就可以编写内联代码

count = 0
for denval in den
  count += d//denval
  d = d % denval

这将返回计数和d中剩余的任何值。如果d小于denval，计数增量将为0，剩余的d不变。当d变为0时，for循环没有中断，但den中几乎没有足够的条目可以忽略测试

  if d < 1:
    break

Answer 3

我们能假定硬币的面额是合理的吗？这个问题的一般情况是允许出现奇怪的硬币面额，如[100，90，1]，而简单的“贪婪”算法不会找到最优解（例如，对于180，最优解是两个90美分的硬币，而简单的贪婪算法会建议一个100美分的硬币和80美分的硬币）。

如果我们可以假设合理的货币（就像任何实际货币一样），那么我建议你使用整数除法和模数的组合来计算每枚硬币的使用数量。

如果我们不能假设合理的货币，那么这个问题是动态规划解决方案的理想选择。在动态规划中，您构建一个记录中间结果的表，与简单的递归解决方案相比，这节省了大量时间。

Skiena的书《Alog算法设计手册》中对动态编程有一个很好的解释。

http://www.algorist.com/

以下是我在网上找到的一些链接：

http://www.avatar.se/molbioinfo2001/dynprog/dynamic.html

http://www.codechef.com/wiki/tutorial-dynamic-programming