我该怎么做“递归"?这个硬币找零问题的循环? [英] How can I do "recursive" for loops in this coin change problem?

问题描述

我正在尝试解决硬币找零问题.您得到一笔钱(例如55美分)，并且必须退回尽可能少的硬币.

Im trying to solve the coin change problem. You get an amount of money (as example 55 cents) and have to give as few coins as possible back.

我的解决方案非常简单(并且可能效率极低).我试图用蛮力去做.

My solution is very simple (and probably extremely inefficient). I tried to do it with brute force.

首先，我尝试使用经过固定编码的固定硬币来完成此任务，并且效果很好

First I tried to do it with fixed coins which are hardcoded and it worked great

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

此后，我尝试使用硬币数组(例如，coins = [25，10，1])进行处理，这是我的问题.

After that I tried to do it with an coins array such as coins = [25, 10, 1] and there is my question.

coins = [25, 10, 1]

def findMinCoins(money, coins):
    n_coins = [(int(money/coin) for coin in coins)]
    smallest = sum(n_coins)

我不知道如何对数组进行for循环.有人可以帮我找到解决办法吗?

I don't know how I should do the for loops with the arrays. Can somebody help me to find a solution?

推荐答案

您可以使用从当前金额中扣除的每个硬币进行递归调用，并从调用的返回值中获取最小值.如果扣减导致钱数少于0，则返回无穷大，以至于将其视为不可行:

You can make recursive calls with each of the coins deducted from the current money, and get the minimum value from the returning value of the calls. Return infinity if the deduction results in money less than 0 so that it would not be considered to be viable:

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作为缓存来记住给定金额和硬币组合的结果，您可以大大提高性能:

The above recursion is slow, however, since it makes a large number of calls with the same amount of money when considering different paths. You can improve the performance dramatically by using a dict as a cache to memoize the results of a given combination of money amount and coins :

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

这篇关于我该怎么做“递归"?这个硬币找零问题的循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！