Change-Making Problem¶
Greedy vs Dynamic Programming
In [1]:
# Greedy approach is fast, but fails for some denominations
import time
t=time.time()
def greedy(Denoms,Amt):
coins = 0
for i in Denoms:
if i <= Amt:
Q,R = divmod(Amt,i)
print(Q,i)
Amt = R
coins += Q
if R==0:
return coins
else:
return -1
amount=63
denominations = [5,10,25,1,6]
denominations.sort(reverse=True)
print(denominations, amount)
print("Min Coins Required:", greedy(denominations,amount))
print("elapsed time: ",time.time()-t)
The true minimum is 5 coins...
In [2]:
# Recursive approach gives the correct answer, but is super slow
import time
t=time.time()
def minCoins(Denoms,Amt):
Mcoins = Amt # assumes coin with value "1"
if Amt in Denoms:
return 1
else:
for i in Denoms: # for i in [x for x in Denoms if x <= Amt]:
if i <= Amt:
Ncoins = 1 + minCoins(Denoms,Amt-i)
if Ncoins < Mcoins:
Mcoins = Ncoins
return Mcoins
amount=63
denominations = [5,10,25,1,6]
denominations.sort(reverse=True)
print(denominations, amount)
print(minCoins(denominations,amount))
print("elapsed time: ",time.time()-t)
In [3]:
# Recursive approach with memoization
import time
t=time.time()
__memo = {}
def minCoins(Denoms,Amt):
if Amt in __memo:
return __memo[Amt]
Mcoins = Amt # assumes coin with value "1"
if Amt in Denoms:
__memo[Amt]=1
return 1
else:
for i in Denoms: # for i in [x for x in Denoms if x <= Amt]:
if i <= Amt:
Ncoins = 1 + minCoins(Denoms,Amt-i)
if Ncoins < Mcoins:
Mcoins = Ncoins
__memo[Amt]=Mcoins
return Mcoins
amount=63
denominations = [5,10,25,1,6]
denominations.sort(reverse=True)
print(denominations, amount)
print(minCoins(denominations,amount))
print(__memo)
print("elapsed time: ",time.time()-t)
