在这个硬币找零问题中，我怎样才能对循环进行“递归”？

Question

我试图解决硬币找零问题。你得到一笔钱（例如 55 美分），并且必须尽可能少地返还硬币。

我的解决方案非常简单（而且可能效率极低）。我试图用蛮力做到这一点。

首先，我尝试用硬编码的固定硬币来做，效果很好

money = 55

def findMinCoins(money):

    nq = int(money/25)

    nd = int(money/10)

    nc = int(money/1)

    smallest = nq + nd + nc

    for q in range(nq+1):

        for d in range(nd+1):

            for c in range(nc+1):

                if q*25 + d*10 + c == money:

                    if q + d + c < smallest:

                        smallest = q + d + c

                        print(q, d, c)

    return smallest

之后，我尝试使用诸如 coin = [25, 10, 1] 之类的硬币数组来做到这一点，这就是我的问题。

coins = [25, 10, 1]

def findMinCoins(money, coins):

    n_coins = [(int(money/coin) for coin in coins)]

    smallest = sum(n_coins)

我不知道我应该如何对数组进行 for 循环。有人可以帮我找到解决方案吗？

Answer 1

您可以使用从当前货币中扣除的每个硬币进行递归调用，并从调用的返回值中获取最小值。如果扣除导致货币小于 0，则返回无穷大，这样它就不会被认为是可行的：def findMinCoins(money, coins):&nbsp; &nbsp; if money < 0:&nbsp; &nbsp; &nbsp; &nbsp; return float('inf')&nbsp; &nbsp; return money and min(findMinCoins(money - coin, coins) for coin in coins) + 1以便：findMinCoins(55, [25, 10, 1])返回：4然而，上面的递归很慢，因为在考虑不同的路径时，它会以相同的金额进行大量调用。您可以通过使用 dict 作为缓存来记忆给定金额和硬币组合的结果，从而显着提高性能：def findMinCoins(money, coins, cache={}):&nbsp; &nbsp; key = money, tuple(coins)&nbsp; &nbsp; if key in cache:&nbsp; &nbsp; &nbsp; &nbsp; return cache[key]&nbsp; &nbsp; if money < 0:&nbsp; &nbsp; &nbsp; &nbsp; number = float('inf')&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; number = money and min(findMinCoins(money - coin, coins) for coin in coins) + 1&nbsp; &nbsp; cache[key] = number&nbsp; &nbsp; return number

Answer 2

从字面上重写你的for循环：>>> money=55>>> lst=[(q+d+c, [q,d,c]) for q in range(int(money/25)+1) for d in range(int(money/10)+1) for c in range(int(money/1)+1) if q*25 + d*10 + c == money]>>> lst[(55, [0, 0, 55]), (46, [0, 1, 45]), (37, [0, 2, 35]), (28, [0, 3, 25]), (19, [0, 4, 15]), (10, [0, 5, 5]), (31, [1, 0, 30]), (22, [1, 1, 20]), (13, [1, 2, 10]), (4, [1, 3, 0]), (7, [2, 0, 5])]然后找到最合适的：>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))[(4, [1, 3, 0])]- - - - - - -编辑概括解决方案：>>> import itertools>>> money=55>>> coins=[25,10,1]>>> lst=[(len(el), el) for num in range(1, money//min(coins)+1) for el in itertools.combinations_with_replacement(coins, num) if sum(el) == money]>>> lst[(4, (25, 10, 10, 10)), (7, (25, 25, 1, 1, 1, 1, 1)), (10, (10, 10, 10, 10, 10, 1, 1, 1, 1, 1)), (13, (25, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (19, (10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (22, (25, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (28, (10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (31, (25, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (37, (10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (46, (10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)), (55, (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1))]>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))[(4, (25, 10, 10, 10))]以上内容非常笼统，对于您的问题，尤其是您的硬币中的问题 - 您可能希望通过将潜在硬币数量的上限替换为任何其他正整数1 cent来大大减少计算次数。money//min(coins)+1例如：>>> coins=[1,2,5,25,50]>>> money=100>>> lst=[(len(el), el) for num in range(1, 5) for el in itertools.combinations_with_replacement(coins, num) if sum(el) == money]>>> lst[(2, (50, 50)), (3, (25, 25, 50)), (4, (25, 25, 25, 25))]>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))[(2, (50, 50))]

Answer 3

可能有一种更 Pythonic 的方式来做到这一点，但一般的递归方法是这样做的：取剩余的金额尝试对每个硬币进行递归调用，以减少金额而不会变为负数。取该集合中最小的结果def findMinCoins(money, coins):&nbsp; &nbsp; if money <= 0:&nbsp; &nbsp; &nbsp; &nbsp;return 0&nbsp; &nbsp; results = []&nbsp; &nbsp; for c in coins:&nbsp; &nbsp; &nbsp; &nbsp; if money >= c:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;results.append(1 + findMinCoins(money-c, coins))&nbsp; &nbsp; results.sort()&nbsp; &nbsp; return results[0] #return the smallest result现在上面唯一的问题是它非常慢，因为它会对先前计算的值进行大量冗余调用。因此，我们将对其进行修改，以便为每个最终结果提供一个查找表，并以递归方式传递。def findMinCoins(money, coins, lookup):&nbsp; &nbsp; if money <= 0:&nbsp; &nbsp; &nbsp; &nbsp;return 0&nbsp; &nbsp; if money in lookup:&nbsp; &nbsp; &nbsp; &nbsp;return lookup[money]&nbsp; &nbsp; results = []&nbsp; &nbsp; for c in coins:&nbsp; &nbsp; &nbsp; &nbsp; if money >= c:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;results.append(1 + findMinCoins(money-c, coins, lookup))&nbsp; &nbsp; results.sort()&nbsp; &nbsp; best = results[0]&nbsp; &nbsp; lookup[money] = best&nbsp; &nbsp; return best测试一些例子：>>> findMinCoins(95,[25,10,5,1], {})5>>> findMinCoins(4,[25,10,5,1], {})4>>> findMinCoins(44,[25,10,5,1], {})7