https://gist.github.com/3343998

coins.py

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)])