ISourceCode

Make the frequent cases fast and the rare case correct

Dynamic Programming Algorithm to find the minimum number of coins to make a certain amount of change out of a given set of denominations

To make a change of 15 from Available denominations 1 2 3 5 we need 3 coins of denomination 5 rather than 5 coins of denomination 3.

SumNeeded = 15
AvailDenominations = [1, 2, 3, 5]

def MinCoins(sum, coinDenominations):
	result = []	
	for i in range(0,sum+1):
		result.append(999)
        
	result[0]=0
	for currentSum in range(1,sum+1):
		for j in range(0,len(AvailDenominations)): 
		  ref = result[currentSum - AvailDenominations[j]] + 1
                  
         	  if AvailDenominations[j] <= currentSum and ref < result[currentSum]:
					                	
				tempA = result[currentSum - AvailDenominations[j]]
				tempB = tempA+1
           			result[currentSum] = tempB
        				
        return result[sum]

SumNeeded = 15
AvailDenominations = [1, 2, 3, 5]
value = MinCoins(SumNeeded, AvailDenominations)
print "Number of coins needed = ",value

OUTPUT:

labuser@ubuntu:~$ python coinproblem.py
Number of coins needed = 3

If input is AvailDenominations = [10, 2, 3, 5] i.e 10+5

labuser@ubuntu:~$ python coinproblem.py
Number of coins needed = 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: