## Tuesday, April 23, 2013

### The minimum coin problem (with prize)

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$

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.

zimpenfish said...

This looks suspiciously like The Knapsack Problem.

Matt said...

Maybe dynamic programming will work for number one?

d = [ 1, 2, 5, ...] # coin values
x = [ 2, 2, 2, ...] # number of coins you have
goal = 170 # how much we are paying

a = [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[y])] + d[x]
if v == goal:
a[y][x] = a[y-1][x] + 1
print a[goal - 1]

William Sewell said...

Yes it looks identical, other than the fact that you can go over 1.70 by no more than one coin. Anonymous said...

Find my solution here:

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)

Asger Drewsen said...

Here's my solution in python: https://gist.github.com/Tyilo/5443729

Asger Drewsen said...
This comment has been removed by the author.
Alex Apetrei said...

I know this is supposed to be a thought experiment :) , but coins are a poor form of currency.

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.

vext01 said...

This reckon this can be solved as a mixed-integer non-linear programming problem:

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...

Dubya said...

GLPK is a nice MINLP solver. The syntax seems pretty reasonable as well. This is the first time I've used it, so this almost certainly isn't optimal:

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;

Josh said...

These can be straightforwardly posed and solved as integer programming problems with a solver such as GLPK.
http://www.takingthefun.com/2013/04/john-graham-cunnings-minimum-coin.html
Problem 1: http://pastebin.com/2hB9KWCx
Problem 3: http://pastebin.com/42dmp4VM

vext01 said...

Hah, I didn't know GLPK could solve non-linear problems. Today I learned...

Josh Jordan said...

vext, this is not a non-linear problem, it is a linear programming problem with integer constraints. Perhaps you meant you didn't know GLPK could solve integer programming problems?

Anatoli Plotnikov said...

I did it with Octave:

https://github.com/panatoli/coin_problem

Matt Hickford said...

I remember reading a similar problem 'pay with as few coins as possible' in the wonderful book The Algorithm Design Manual. Cashiers know the greedy algorithm (keep using the biggest coin you can) is optimal for British currency. However imagine trying to pay 6 in a fictional currency with denominations [4,3,1]. The greedy algorithm gives 4+1+1 which isn't as good as 3+3. I don't know if any real world currencies are so perverse.

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

Matt Hickford said...
This comment has been removed by the author.
Matt Hickford said...
This comment has been removed by the author.
placement jump said...

Here coin change problem is imoplemented in java and its realy easy to understand.
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;

}