The minimum coin problem solution in python

min-coin-bruteforce.py

coins_values = [2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01]
coins_amount = [1, 2, 2,   3,   1,   2,    2,    2   ]

price = 1.7


import itertools

total_coins = 0
coins_list = []
for value, amount in itertools.izip(coins_values, coins_amount):
	total_coins += amount
	coins_list += [value] * amount

def get_sum(prev_coins, coins_used, coins_sum, coin):
	if coins_sum > price:
		if coins_sum >= price + prev_coins[coins_used - 1]:
			return -1, []
		else:
			return coins_used, prev_coins
	else:
		if coin == total_coins:
			if coins_sum < price:
				return -1, []
			else:
				return coins_used, prev_coins
		else:
			next_coin = coins_list[coin]
			used1, coins1 = get_sum(prev_coins + [next_coin], coins_used + 1, coins_sum + next_coin, coin + 1)
			used2, coins2 = get_sum(prev_coins,                      coins_used,     coins_sum,      coin + 1)
			if used1 >= used2:
				return used1, coins1
			else:
				return used2, coins2

coins_used, coins = get_sum([], 0, 0, 0)
print "Coins: ", coins
print "Amount: ", coins_used
print "Total value: ", sum(coins)

Ah I see what you're doing there - should have thought of this.