I came across this video on youtube that talks about greedy algorithms and as an example presents the classic change making problem.
It is a very informative introductory video and I would recommend it to anyone who is interested in algorithms. And while you are at it please support the CS50 youtube channel by subscribing and viewing their videos. They are doing a darn good job of providing basic educational material in computer science for young students interested in the field. The problem statement essentially boils down to this: How can you make change for a given amount of money by using the least number of coins, where the coin denominations are fixed. For example, given that you have a sufficient supply of 1, 5, 10, 25 and 50 cent coins, how would be make change for 80 cents using the least number of coins? By observation we can see that a 50 cent, a quarter and a nickel with make up 80 cents and this uses the least number of coins. The solution for this problem can be algorithmically provided by using the so called greedy algorithm. But how would you approach the general problem? How many ways can you make change for a given amount when a certain number of coin denominations are allowed. This is a problem that lends itself to a recursive solution. This got me interested and I decided to whip up a quick program in my most recent favorite language, Python. The code is shown below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
def noofSums(n,S,currDict): if n==0: target=0 Pstring="" for key in currDict: if currDict[key]!=0: Pstring = Pstring + str(key) + "*" + str(currDict[key]) + " + " target = target+key*currDict[key] Pstring = Pstring[:-3] print Pstring, "=", target return 1 elif n<0: return 0 if len(S)==0: return 0 Scopy = S.copy() trial = Scopy.pop() ret_value = 0 for i in range(0,n/trial+1): currDict[trial]=i ret_value = ret_value + noofSums(n-i*trial,Scopy,currDict) del currDict[trial] return ret_value if __name__ == '__main__': S={5,10,25,50} n=80 print n, S result = noofSums(n,S,dict()) print "Total combinations: ", result |
Pardon the dismal state of commenting as I only had a few minutes to work on the code. The program could be run using the command python CoinChange.py assuming you have python installed on your computer and the code is saved in a file named CoinChange.py. Note that, in the code I have removed the option of 1 cent coins (line 33) as it resulted in a very large number of solutions. The program will print out the following output, listing the various ways you can make change for 80 cents using 5, 10, 25 and 50 cent coins.
80 set([25, 50, 10, 5]) 5*16 = 80 10*1 + 5*14 = 80 10*2 + 5*12 = 80 10*3 + 5*10 = 80 10*4 + 5*8 = 80 10*5 + 5*6 = 80 10*6 + 5*4 = 80 10*7 + 5*2 = 80 10*8 = 80 50*1 + 5*6 = 80 50*1 + 10*1 + 5*4 = 80 50*1 + 10*2 + 5*2 = 80 50*1 + 10*3 = 80 25*1 + 5*11 = 80 25*1 + 10*1 + 5*9 = 80 25*1 + 10*2 + 5*7 = 80 25*1 + 10*3 + 5*5 = 80 25*1 + 10*4 + 5*3 = 80 25*1 + 10*5 + 5*1 = 80 25*1 + 50*1 + 5*1 = 80 25*2 + 5*6 = 80 25*2 + 10*1 + 5*4 = 80 25*2 + 10*2 + 5*2 = 80 25*2 + 10*3 = 80 25*3 + 5*1 = 80 Total combinations: 25
As you can see, there are 25 unique ways of making change for 80 cents using the four given denominations. A trivial modification to the code will also print the number of coins used by each solution and we can again verify that we need at least 3 coins to make change for 80 cents.
Leave a Reply