Solve coin problem from http://blog.jgc.org/2013/04/the-minimum-coin-problem-with-prize.html

coins.py

#!python
# -*- coding: utf-8 -*-

# http://blog.jgc.org/2013/04/the-minimum-coin-problem-with-prize.html
# I have in my pocket the following British coins: one £2, two £1, two 50p, three 20p, one 10p, two 5p, two 2p and two 1p. I wish to buy a copy of today's paper at a cost of £1.70.
# What is the maximum number of coins I can use to pay for the paper? With the restriction that I pay in a reasonable manner (e.g. I could give exactly £1.70 or an amount greater than that but without giving extraneous coins: e.g. giving the seller all the coins would not be acceptable, but giving him one £1 an two 50ps and expecting 30p in change is OK). The reasonable manner is simply: if I give the seller a set of coins he should not be able to return any to me without the sum of the remaining coins dropping below £1.70.

from collections import Counter, OrderedDict

def solve_exact(coins, P, f=len):
    "Return a subset of coins summing to exactly P of maximal size (or maximising the function f)"
    coins = Counter(coins)
    denominations = coins.keys()

    # Think! An optimal solution for P contains an optimal solution for P-d, for some coin d. (Assuming the function f is additive). So can solve by dynamic programming.

    optimal_by_price = [None for i in range(0,P+1)]
    optimal_by_price[0] = Counter()

    for p in range(1, P+1):
        potentials = list()

        for d in denominations:
            # try to make price p by spending coin value d on top of an optimal solution for p-d
            if p-d < 0:
                continue

            base = optimal_by_price[p-d]
            if base == None:
                # we previously concluded p-d is impossible to make
                continue

            remaining = coins - base
            if d not in remaining:
                # no coins value d left to spend
                continue

            potential = base + Counter([d])
            assert sum(potential.elements()) == p
            assert potential <= coins
            potentials.append(potential)

        if potentials:
            optimal_by_price[p] = max(potentials, key=f)

    return optimal_by_price[P]

def solve_allowing_change(coins, P, f=len):
    "Return a subset of coins summing to at least P, with the constraint that removing any coin makes the sum drop below P. Of possible subsets, return one of maximal size."
    coins = Counter(coins)
    denominations = coins.keys()

    # aha! Solve the exact problem for each Q >= P (being careful not to break the constraint), and choose the best of those.

    possibles = []
    exact = solve_exact(coins, P, f) # make P exactly
    if exact != None:
        possibles.append(exact)  

    for extra in range(1, max(denominations)+1):
        # try making P + extra
        # to make sure the constraint isn't be broken, use only coins greater than extra 
        careful_coins = Counter([x for x in coins.elements() if x > extra])
        assert careful_coins <= coins

        possible = solve_exact(careful_coins, P+extra, f)
        if possible == None:
            continue

        possibles.append(possible)

    if possibles:
        return max(possibles, key=f)

def prettify(counter):
    ordered = sorted(counter.elements(), reverse=True)
    return "sum(%s) = %s" % (ordered, sum(counter.elements()))

if __name__ == "__main__":
    johns_pocket = Counter({200:1, 100:2, 50:2, 20:3, 10:1, 5:2, 2:2, 1:2})
    paper = 170
    print "Pay %d with coins %s" % (paper, sorted(johns_pocket.elements()))
    print prettify(solve_exact(johns_pocket, paper))
    print prettify(solve_allowing_change(johns_pocket, paper))

    print
    print "An example where you can use more coins by paying more than asked"
    pocket = Counter({5:3, 7:2})
    chocolate = 14
    print "Pay %d with coins %s" % (chocolate, sorted(pocket.elements()))
    print prettify(solve_exact(pocket, chocolate))
    print prettify(solve_allowing_change(pocket, chocolate))