saml/coins.py

## 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