Skip to content

Instantly share code, notes, and snippets.

# hickford/coins.py Last active Dec 17, 2015

 #!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 = 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))
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.