bank.py

from collections import Counter

def withdraw_one(amount):
	bills = [100,50,20]
	
	memo = [amount + 1] * (amount + 1)
	bills_results = [[]] * (amount+1)
	d = {100:0, 50:0, 20:0}

	memo[0] = 0

	for i in range(1, amount+1):
		for bill in bills:
			if i >= bill and memo[i - bill] + 1 < memo[i]:
				memo[i] = memo[i-bill] + 1
				bills_results[i] = bills_results[i-bill] + [bill]

	if memo[amount] == amount + 1:
		return []
	
	for i in bills_results[amount]:
		d[i] += 1
	return [d[100], d[50], d[20]]

def withdraw(amount):
	bills = [100,50,20]

	result = []

	def backtrack(end, remain, cur_result):
		if end < 0:
			return
		if remain == 0:
			result.append(cur_result)
			return
		if remain >= bills[end]:
			backtrack(end, remain - bills[end], cur_result + [bills[end]])
		backtrack(end - 1, remain, cur_result)

	backtrack(len(bills)-1, amount, [])
	m = 0
	for rs in range(len(result)):
		if len(result[m]) > len(result[rs]):
			m = rs
	# just for fun; rather writing another loop 
	d = Counter(result[m])
	return [d[100], d[50], d[20]]

def main():
	print(withdraw(40))
	print(withdraw(250))
	print(withdraw(260))
	print(withdraw(230))
	print(withdraw(60))

def run_test():
	nums = [40, 250, 260, 230, 60]
	for num in nums:
		print(withdraw(num) == withdraw_one(num))

if __name__ == '__main__':
	#main()
	run_test()
	#print(withdraw(230))