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.

Looks like it's: two 50p, three 20p, one 5p, two 2p and one 1p. That gives away 9 coins from the 15 coins I have.

The general statement of this problem is as follows. There are \(n\) coins in a currency: \(d_0\) to \(d_{n-1}\) are the denominations of the coins (normalize all to a single unit, e.g. a £2 coin would have denomination 200) where \(d_0 < d_1 < ... < d_{n-1}\). I have \(x_0\) to \(x_{n-1}\) of each coin (\(x_i \ge 0\)). I wish to pay for an item costing \(P\).

Problem 1 (giving away a maximum number of coins with the exact amount): Find amounts \(g_0\) to \(g_{n-1}\) where \(g_i \le x_i\) and

$$\sum_{i=0}^{n-1} g_i \times d_i = P$$

and minimizes

\[\sum_{i=0}^{n-1} (x_i - g_i)\]

Problem 2 (ending up with the minimum number of coins when change is optionally given): Find amounts \(g_0\) to \(g_{n-1}\) where \(g_i \le x_i\) and

\[\sum_{i=0}^{n-1} g_i \times d_i \ge P\]

and minimizes

\[\sum_{i=0}^{n-1} (x_i - g_i) + c_i\]

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.

Looks like it's: two 50p, three 20p, one 5p, two 2p and one 1p. That gives away 9 coins from the 15 coins I have.

The general statement of this problem is as follows. There are \(n\) coins in a currency: \(d_0\) to \(d_{n-1}\) are the denominations of the coins (normalize all to a single unit, e.g. a £2 coin would have denomination 200) where \(d_0 < d_1 < ... < d_{n-1}\). I have \(x_0\) to \(x_{n-1}\) of each coin (\(x_i \ge 0\)). I wish to pay for an item costing \(P\).

Problem 1 (giving away a maximum number of coins with the exact amount): Find amounts \(g_0\) to \(g_{n-1}\) where \(g_i \le x_i\) and

$$\sum_{i=0}^{n-1} g_i \times d_i = P$$

and minimizes

\[\sum_{i=0}^{n-1} (x_i - g_i)\]

Problem 2 (ending up with the minimum number of coins when change is optionally given): Find amounts \(g_0\) to \(g_{n-1}\) where \(g_i \le x_i\) and

\[\sum_{i=0}^{n-1} g_i \times d_i \ge P\]

\[\sum_{i=0}^{n-1} (x_i - g_i) + c_i\]

where \(c_i\) are the number of coins of change given by the newspaper seller in each denomination \(d_i\).

Bonus: take into account the weight of each coin and minimize the weight in my pocket not the number of coins.

Prize: a free copy of my book, The Geek Atlas, to be picked by me on May 15, 2013 from algorithms and implementations posted in the comments of this blog post.

Prize: a free copy of my book, The Geek Atlas, to be picked by me on May 15, 2013 from algorithms and implementations posted in the comments of this blog post.

## Comments

d = [ 1, 2, 5, ...] # coin values

x = [ 2, 2, 2, ...] # number of coins you have

goal = 170 # how much we are paying

a[1][1] = [1, 0, 0, ...] # assuming we start with a one piece

for y in range(goal):

for x in range(len(d)):

v = [i*j for i,j in zip(d,a[1][y])] + d[x]

if v == goal:

a[1][y][x] = a[1][y-1][x] + 1

print a[1][goal - 1]

https://gist.github.com/mihi-tr/5443534

I do think (untested) that spending the exact number of coins has you _always_ ending up with less coins (in this combination)

Heavy fiddly and easily not there when you need them ... also there is an apparent need for an algorithm to describe how to best get rid of them :)

May I suggest some form of NFC payment ? preferably directly from a bank account and not through VISA or MASTERCARD ,adopted at least on a country level if not at a world wide level.

maximise: c1 + c2 + ... + c14 + c15;

gave = 200 * c1 + 100 * c2 + ... + 1 * c14 + 1 * c15;

change = gave - 170;

c1 * change <= 199;

c2 * change <= 99;

c3 * change <= 99;

c4 * change <= 49;

c5 * change <= 49;

c6 * change <= 19;

c7 * change <= 19;

c8 * change <= 19;

c9 * change <= 9;

c10 * change <= 4;

c11 * change <= 4;

c12 * change <= 1;

c13 * change <= 1;

c14 * change <= 0;

c15 * change <= 0;

where c1, ..., c15 are binary decision variables.

I think this is correct, but I don't have a MINLP solver set up to try it. They tend to have a lot of obscure dependencies that need to be built by hand...

set COINS;

param Value {i in COINS};

param Count {i in COINS};

var x {i in COINS} >=0, integer;

maximize z: sum{i in COINS} x[i];

s.t. Payout: sum{i in COINS} Value[i]*x[i] >= 170;

s.t. Use {i in COINS} : x[i] <= Count[i];

s.t. Enough {i in COINS} : sum{j in COINS} Value[j]*x[j] <= 169 + Value[i];

data;

set COINS := twolb onelb fiftyp twentyp tenp fivep twop onep;

param Value:= twolb 200 onelb 100 fiftyp 50 twentyp 20 tenp 10 fivep 5

twop 2 onep 1;

param Count:= twolb 1 onelb 2 fiftyp 2 twentyp 3 tenp 1 fivep 2 twop 2

onep 2;

end;

http://www.takingthefun.com/2013/04/john-graham-cunnings-minimum-coin.html

Problem 1: http://pastebin.com/2hB9KWCx

Problem 2: http://pastebin.com/Dh6NWVaD

Problem 3: http://pastebin.com/42dmp4VM

https://github.com/panatoli/coin_problem

This problem is cool too. Allowing overpayment stumped me for a while. By the way, I'm not sure the constraint "he should not be able to return any to me without the sum of the remaining coins dropping below £1.70" is correctly reproduced in the mathematical statement 'problem 2' (it should be a constraint rather than mixed in with the utility function).

Anyway, here are my solutions (Python) to the exact problem and the allowing change problem. The wonderthought was that you can solve the allowing change problem by solving the exact problem for varying amounts of overpay. Just be careful only to use coins bigger than the amount you overpay, so not to break the change constraint.

https://gist.github.com/matt-hickford/5560996

@Michael sometimes it is optimal to overpay:

An example where you can use more coins by paying more than asked

Pay 14 with coins [5, 5, 5, 7, 7]

sum([7, 7]) = 14 # can only use 2 coins, if being exact

sum([7, 5, 5]) = 17 # can use with 3 coins, if overpaying

http://placementjump.blogspot.in/2013/08/coin-change-problem-in-java-dynamic.html

int minimum(int x,int y,int z){

int min;

if(x>=y && z>=y)

return y;

else

if(x>=z)

return z;

else

return x;

}