greedy solution to the first problem at http://blog.jgc.org/2013/04/the-minimum-coin-problem-with-prize.html

greedy.py

#!/usr/bin/python

# Does this work?
# http://blog.jgc.org/2013/04/the-minimum-coin-problem-with-prize.html

coins = [200,50,50,100,100,20,20,20,10,5,5,2,2,1,1]
coins.sort()
coins.reverse()

paper = 170

fortune = sum(coins)
print "my fortune is %d" % fortune

payback = fortune - paper
print "vendor can give back at most %d" % payback

change = []

for coin in coins:
    if (sum(change) + coin) <= payback:
        change.append(coin)

print "change", change
print "price paid", sum(coins) - sum(change)

for coin in change:
    coins.remove(coin)

print "coins deposited",coins
print "num deposited %s" % len(coins)