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

### Like this:

Like Loading...

*Related*