Understanding change-making algorithm


Question

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?

1
17
12/28/2016 2:06:20 AM

Accepted Answer

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
14
2/21/2013 1:19:24 AM

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:

  1. 3+2
  2. 3+1+1
  3. 2+2+1
  4. 1+2+1+1
  5. 1+1+1+1+1

while the recursive version counts:

  1. 3+2
  2. 2+3
  3. 3+1+1
  4. 1+3+1
  5. 1+1+3
  6. 2+1+2
  7. 1+1+2
  8. 2+2+1
  9. 2+1+1+1
  10. 1+2+1+1
  11. 1+1+2+1
  12. 1+1+1+2
  13. 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]

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon