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

Question

我试图解决硬币找零问题。你得到一笔钱（例如 55 美分），并且必须尽可能少地返还硬币。我的解决方案非常简单（而且可能效率极低）。我试图用蛮力做到这一点。首先，我尝试用硬编码的固定硬币来做，效果很好money = 55def 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):

    if money < 0:

        return float('inf')

    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={}):

    key = money, tuple(coins)

    if key in cache:

        return cache[key]

    if money < 0:

        number = float('inf')

    else:

        number = money and min(findMinCoins(money - coin, coins) for coin in coins) + 1

    cache[key] = number

    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):

    if money <= 0:

       return 0

    results = []

    for c in coins:

        if money >= c:

           results.append(1 + findMinCoins(money-c, coins))

    results.sort()

    return results[0] #return the smallest result

现在上面唯一的问题是它非常慢，因为它会对先前计算的值进行大量冗余调用。因此，我们将对其进行修改，以便为每个最终结果提供一个查找表，并以递归方式传递。

def findMinCoins(money, coins, lookup):

    if money <= 0:

       return 0

    if money in lookup:

       return lookup[money]

    results = []

    for c in coins:

        if money >= c:

           results.append(1 + findMinCoins(money-c, coins, lookup))

    results.sort()

    best = results[0]

    lookup[money] = best

    return best

测试一些例子：

>>> findMinCoins(95,[25,10,5,1], {})

5

>>> findMinCoins(4,[25,10,5,1], {})

4

>>> findMinCoins(44,[25,10,5,1], {})

7