Understanding change-making algorithm

I was looking for a good solution to the Change-making problem and I found this code(Python):

target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin,target+1):
        ways[i]+=ways[i-coin]
print(ways[target])

I have no problems understanding what the code literally does,but I can't understand WHY it works. Anyone can help?

To get all possible sets that elements are equal to 'a' or 'b' or 'c' (our coins) that sum up to 'X' you can:

Take all such sets that sum up to X-a and add an extra 'a' to each one.
Take all such sets that sum up to X-b and add an extra 'b' to each one.
Take all such sets that sum up to X-c and add an extra 'c' to each one.

So number of ways you can get X is sum of numbers of ways you can get X-a and X-b and X-c.

ways[i]+=ways[i-coin]

Rest is simple recurrence.

Extra hint: at the start you can get set with sum zero in exactly one way (empty set)

ways = [1]+[0]*target

This is a classical example of dynamic programming. It uses caching to avoid the pitfall of counting things like 3+2 = 5 twice (because of another possible solution: 2+3). A recursive algorithm falls into that pitfall. Let's focus on a simple example, where target = 5 and coins = [1,2,3]. The piece of code you posted counts:

3+2
3+1+1
2+2+1
1+2+1+1
1+1+1+1+1

while the recursive version counts:

3+2
2+3
3+1+1
1+3+1
1+1+3
2+1+2
1+1+2
2+2+1
2+1+1+1
1+2+1+1
1+1+2+1
1+1+1+2
1+1+1+1+1

Recursive code:

coinsOptions = [1, 2, 3]
def numberOfWays(target):
    if (target < 0):
        return 0
    elif(target == 0):
        return 1
    else:
        return sum([numberOfWays(target - coin) for coin in coinsOptions])
print numberOfWays(5)

Dynamic programming:

target = 5
coins = [1,2,3]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin, target+1):
        ways[i]+=ways[i-coin]
print ways[target]

The main idea behind the code is the following: "On each step there are ways ways to make change of i amount of money given coins [1,...coin]".

So on the first iteration you have only a coin with denomination of 1. I believe it is evident to see that there is only one way to give a change having only these coins for any target. On this step ways array will look like [1,...1] (only one way for all targets from 0 to target).

On the next step we add a coin with denomination of 2 to the previous set of coins. Now we can calculate how many change combinations there are for each target from 0 to target. Obviously, the number of combination will increase only for targets >= 2 (or new coin added, in general case). So for a target equals 2 the number of combinations will be ways[2](old) + ways[0](new). Generally, every time when i equals a new coin introduced we need to add 1 to previous number of combinations, where a new combination will consist only from one coin.

For target > 2, the answer will consist of sum of "all combinations of target amount having all coins less than coin" and "all combinations of coin amount having all coins less than coin itself".

Here I described two basic steps, but I hope it is easy to generalise it.

Let me show you a computational tree for target = 4 and coins=[1,2]:

ways[4] given coins=[1,2] =

ways[4] given coins=[1] + ways[2] given coins=[1,2] =

1 + ways[2] given coins=[1] + ways[0] given coins=[1,2] =

1 + 1 + 1 = 3

So there are three ways to give a change: [1,1,1,1], [1,1,2], [2,2].

The code given above is completely equivalent to the recursive solution. If you understand the recursive solution, I bet you understand the solution given above.

Understanding change-making algorithm

Related

Recent Posts