Skip to content

Instantly share code, notes, and snippets.

@lessandro
Created August 15, 2012 18:38
Show Gist options
  • Save lessandro/3362219 to your computer and use it in GitHub Desktop.
Save lessandro/3362219 to your computer and use it in GitHub Desktop.
class Solver(object):
def __init__(self, coins):
self.coins = coins
self.path = {}
self.memo = {}
def cost(self, cents):
if cents == 0:
return 0
if cents < 0:
return float('inf')
if cents in self.memo:
return self.memo[cents]
best_coin = None
best_total = float('inf')
for coin in self.coins:
total = 1 + self.cost(cents - coin)
if total < best_total:
best_coin = coin
best_total = total
self.path[cents] = best_coin
self.memo[cents] = best_total
return best_total
def solve(self, cents):
if self.cost(cents) == float('inf'):
return []
ls = []
while cents != 0:
ls.append(self.path[cents])
cents -= self.path[cents]
return reversed(sorted(ls))
if __name__ == '__main__':
solver = Solver([1, 5, 10, 25])
for cents in [123, 7, 39]:
print " ".join([str(n) for n in solver.solve(cents)])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment