How can I do “recursive” for loops in this coin ch

问题:

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

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)

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

回答1:

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

so that:

findMinCoins(55, [25, 10, 1])

returns:

4

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

回答2:

Literally re-writing your for loops:

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

Then to find best fit:

>>> list(filter(lambda x: x[0]==min(el[0] for el in lst), lst))
[(4, [1, 3, 0])]

-------------EDIT

To generalize the solution:

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

The above is very general, and for your problem, especially that you have 1 cent among your coins - you might want to reduce number of calculation greatly by replacing cap on potential number of coins from money//min(coins)+1 to any other positive integer.

For example:

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

回答3:

There may be a more pythonic way to do this, but the general recursive approach is to do this:

Take the amount of money remaining Try a recursive calls for each coin that reduces the amount without going negative. Take the smallest result of that set

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

Now the only issue with the above is that it's VERY SLOW because it will make a lot of redundant calls for values that were previously computed. So we'll amend that to have a lookup table for each final result and have that passed recursively as well.

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

Testing out some examples:

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