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 = +*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:
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.
Rest is simple recurrence.
Extra hint: at the start you can get set with sum zero in exactly one way (empty set)
ways = +*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:
while the recursive version counts:
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)
target = 5 coins = [1,2,3] ways = +*target for coin in coins: for i in range(coin, target+1): ways[i]+=ways[i-coin] print ways[target]