def exhaustiveChange(amount, denominations):
bestN = 100
count = [0 for i in xrange(len(denominations))]
while True:
for i, coinValue in enumerate(denominations):
count[i] += 1
if (count[i]*coinValue < 100):
break
count[i] = 0
n = sum(count)
if n == 0:
break
value = sum([count[i]*denominations[i] for i in xrange(len(denominations))])
if (value == amount):
if (n < bestN):
bestN = n
return bestN
%timeit exhaustiveChange(42, [25,20,10,5,1])
def branchAndBoundChange(amount, denominations):
bestN = amount
count = [0 for i in xrange(len(denominations))]
while True:
for i, coinValue in enumerate(denominations):
count[i] += 1
if (count[i]*coinValue < amount):
break
count[i] = 0
n = sum(count)
if n == 0:
break
if (n > bestN):
continue
value = sum([count[i]*denominations[i] for i in xrange(len(denominations))])
if (value == amount):
if (n < bestN):
bestN = n
return bestN
%timeit branchAndBoundChange(42, [25,20,10,5,1])
def RecursiveChange(M, c):
if (M == 0):
return [0 for i in xrange(len(c))]
smallestNumberOfCoins = M+1
for i in xrange(len(c)):
if (M >= c[i]):
thisChange = RecursiveChange(M - c[i], c)
thisChange[i] += 1
if (sum(thisChange) < smallestNumberOfCoins):
bestChange = thisChange
smallestNumberOfCoins = sum(thisChange)
return bestChange
%timeit RecursiveChange(42, [25,20,10,5,1])
def DPChange(M, c):
change = [[0 for i in xrange(len(c))]]
for m in xrange(1,M+1):
bestNumCoins = m+1
for i in xrange(len(c)):
if (m >= c[i]):
thisChange = [x for x in change[m - c[i]]]
thisChange[i] += 1
if (sum(thisChange) < bestNumCoins):
change[m:m] = [thisChange]
bestNumCoins = sum(thisChange)
return change[M]
%timeit DPChange(42, [25,20,10,5,1])