Skip to content

Instantly share code, notes, and snippets.

Created February 26, 2016 11:20
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
def dpMakeChange(coinValueList,change,mincoins,coinsused):
for cents in range(change+1):
coincount = cents
newcoin = 1
for j in [c for c in coinValueList if c <= cents]:
if mincoins[cents-j] + 1 <coincount:
coincount = mincoins[cents-j]+1
newcoin = j
mincoins[cents] = coincount
coinsused[cents] = newcoin
return mincoins[change]
def printcoins(coinsused, change):
coin = change
coinlist = []
while coin > 0:
thiscoin = coinsused[coin]
coin = coin - thiscoin
return coinlist
def Change(coins, amount):
coinsused = [0]*(amount+1)
coincount = [0]*(amount+1)
dpMakeChange(coins, amount, coincount, coinsused)
return (printcoins(coinsused, amount))
def main():
amount = 63
coins = [1, 5, 10, 21, 25]
print("They are:")
print (Change(coins, amount))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment