Recursive change-making algorithm

Question

Given a target amount and a list of coin denominations, my code is supposed to find the fewest coins needed to reach the target amount.

Examples:

C(78, [1, 5, 10, 25, 50]) = 6
- we can make 78 from 3x25 + 3x1, so 6 coins are required
C(48, [1, 7, 24, 42]) = 2
- 48 = 2x24, so 2 coins are sufficient
C(35, [1, 3, 16, 30, 50]) = 3
- we can make 35 from 2x16 + 1x3, so 3 coins suffice

I made the code with for loops, but how do I make it recursive?

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1
        return cdict[i]
    else:
        min = 0
        for cj in coins:
            result = C(i - cj, coins)
            if result != 0:
                if min == 0 or (result + 1) < min:
                    min = 1 + result
        cdict[i] = min
        return cdict[i]

It already is recursive. You're calling `C` from within itself. Am I missing something here? — Blender, Sep 20 '12 at 20:19
'The least amount of coins that are needed'? Needed for what? This is really poorly explained. — Gareth Latty, Sep 20 '12 at 20:20
@Lattyware: I think the least number of coins from the list that add up to equal that number. — Blender, Sep 20 '12 at 20:21
Presumably it is the least amount of coins needed to add up to `i`. It's a fairly common example problem for dynamic programming. — Kevin, Sep 20 '12 at 20:21

Óscar López · Accepted Answer · 2012-09-20T20:44:05.660

It's the change-making problem. Here's the standard recursive solution, V is the list of coins and C the target amount of money:

def min_change(V, C):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)

And this is an optimized version, using dynamic programming:

def min_change(V, C):
    m, n = len(V)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - V[i-1]] if j - V[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]

Both implementations will always return the optimal solution, but the second one will be much faster for large inputs. Notice that the greedy algorithm suggested in other answers gives an optimal solution only for certain combinations of currency - for instance, it works for the American coins.

Thank you. this is exactly what i needed. Just a few questions, where are you getting the variables i, aC from and what do they mean? — user1681664, Sep 20 '12 at 20:46
Look at the last line in the function, the part where `min_coins()` is being called. Initially, `i = len(V)-1` and `aC = C`. `min_coins()` is an internal helper function — Óscar López, Sep 20 '12 at 21:15

score 2 · Answer 2 · answered Sep 20 '12 at 20:23

2

Try using a greedy algorithm (largest coins first). Remove the coin from the list after you apply to the total and call the function again from within.

answered Sep 20 '12 at 20:23

brad-tot

783
7
9

3

The greedy algorithm does not always give the best answer. For instance, with 1, 6, 7, and 10 cent coins, what is the least number of coins needed to get to 13 cents? The greedy method says {10,1,1,1}, But the true answer is {7,6}. – Kevin Sep 20 '12 at 20:29
It does for real denominations of coins ... but from an academic standpoint that is correct – Joran Beasley Sep 20 '12 at 20:32
1

The greedy algorithm gives an optimal solution only for certain combinations of currency. For instance, it works for the American coins. – Óscar López Sep 20 '12 at 20:36
Greedy approach will not give an optimal solution. Its definitely a question on **Dynamic Programming**. – Srijan Sep 20 '12 at 21:05
Check my greedy implementation above: `print(greedy((1, 6, 7, 10), 13))` gives: {6: 1, 7: 1}. If it does not give you the right answer it only means that you were not able to implement it correctly. Greedy means it will search all possible ways of solving the problem and then choosing optimal. – dgrigonis May 12 '17 at 12:21

score 0 · Answer 3 · answered May 12 '17 at 12:17

So the best place to look for dynamic programming implementation is: interactive python

However, after a bit of testing I found that it is not the fastest solution. The good thing about it is that one run is enough to find values for all change values up needed amount.

My favourite is still to use recursion with caching:

from collections import defaultdict
from functools import lru_cache


@lru_cache(maxsize=1024)
def greedy(coin_list, change):
    if change in coin_list:
        return defaultdict(int, [(change, 1)])
    else:
        min_coins = change
        for c in [coin for coin in coin_list if coin < change]:
            result_min1 = greedy(coin_list, change - c)
            num_coins = 1 + sum(result_min1.values())
            if num_coins <= min_coins:
                min_coins = num_coins
                result = defaultdict(int, [(c, 1)])
                for c1, n in result_min1.items():
                    result[c1] += n
        return result

Recursive change-making algorithm

3 Answers3

Linked