Skip to content

Instantly share code, notes, and snippets.

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

Embed
What would you like to do?
#!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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.