Skip to content

Instantly share code, notes, and snippets.

@KartikTalwar

KartikTalwar/GreedyCoin.py

Created July 28, 2012 00:07
Show Gist options
  • Save KartikTalwar/3191145 to your computer and use it in GitHub Desktop.
Save KartikTalwar/3191145 to your computer and use it in GitHub Desktop.
Download ZIP
Simple Greedy Coin Algorithm
Raw
GreedyCoin.py
def bestChange(denominations, amount):
if amount == 0:
return []
for i in denominations:
if i <= amount:
return [i] + bestChange(denominations, amount-i)
denominations = [100, 50, 20, 10, 5, 2, 1]
amount = 109
print bestChange(denominations, amount)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment