saml · August 15, 2012 20:47 · saml · Aug 15, 2012 · saml · Aug 15, 2012
diff --git a/coins.py b/coins.py
 import sys
 sys.setrecursionlimit(999999999)
 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__':
    with open(sys.argv[1], 'r') as input_file:
        input_file.readline()
        solver = Solver([int(x,10) for x in input_file.readline().split()])
        
        input_file.readline()
        for x in input_file:
            try:
                x = x.strip()
                print(x + ' => ' + ' '.join(str(answer) for answer in solver.solve(int(x,10))))
            except:
                pass
	import sys
	sys.setrecursionlimit(999999999)
	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__':
	with open(sys.argv[1], 'r') as input_file:
	input_file.readline()
	solver = Solver([int(x,10) for x in input_file.readline().split()])

	input_file.readline()
	for x in input_file:
	try:
	x = x.strip()
	print(x + ' => ' + ' '.join(str(answer) for answer in solver.solve(int(x,10))))
	except:
	pass