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][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]

Unknown 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)
Unknown said…
Here's my solution in python: https://gist.github.com/Tyilo/5443729
Unknown said…
This comment has been removed by the author.
Unknown 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 Jordan 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?
Unknown said…
I did it with Octave:

https://github.com/panatoli/coin_problem
Earth 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
Earth said…
This comment has been removed by the author.
Earth said…
This comment has been removed by the author.
raj 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;

}
Etherdesk said…
Hi there to everybody, it’s my first go to see of this web site; this weblog consists of awesome and in fact good stuff for visitors. Hurrah, that’s what I was exploring for, what stuff! Existing here at this blog, thanks admin of this web site. You can also visit Best Coin For Mining for more EtherDesk related information and knowledge.

Your last name contains invalid characters

My last name is "Graham-Cumming". But here's a typical form response when I enter it: Does the web site have any idea how rude it is to claim that my last name contains invalid characters? Clearly not. What they actually meant is: our web site will not accept that hyphen in your last name. But do they say that? No, of course not. They decide to shove in my face the claim that there's something wrong with my name. There's nothing wrong with my name, just as there's nothing wrong with someone whose first name is Jean-Marie, or someone whose last name is O'Reilly. What is wrong is that way this is being handled. If the system can't cope with non-letters and spaces it needs to say that. How about the following error message: Our system is unable to process last names that contain non-letters, please replace them with spaces. Don't blame me for having a last name that your system doesn't like, whose fault is that? Saying "Your

All the symmetrical watch faces (and code to generate them)

If you ever look at pictures of clocks and watches in advertising they are set to roughly 10:10 which is meant to be the most attractive (smiling!) position for the hands . They are actually set to 10:09.14 if the hands are truly symmetrical. CC BY 2.0 image by Shinji I wanted to know what all the possible symmetrical watch faces are and so I wrote some code using Processing. Here's the output (there's one watch face missing, 00:00 or 12:00, because it's very boring): The key to writing this is to figure out the relationship between the hour and minute hands when the watch face is symmetrical. In an hour the minute hand moves through 360° and the hour hand moves through 30° (12 hours are shown on the watch face and 360/12 = 30). The core loop inside the program is this:   for (int h = 0; h <= 12; h++) {     float m = (360-30*float(h))*2/13;     int s = round(60*(m-floor(m)));     int col = h%6;     int row = floor(h/6);     draw_clock((r+f)*(2*col+1), (r+f)*(row*2+1),

The Elevator Button Problem

User interface design is hard. It's hard because people perceive apparently simple things very differently. For example, take a look at this interface to an elevator: From flickr Now imagine the following situation. You are on the third floor of this building and you wish to go to the tenth. The elevator is on the fifth floor and there's an indicator that tells you where it is. Which button do you press? Most people probably say: "press up" since they want to go up. Not long ago I watched someone do the opposite and questioned them about their behavior. They said: "well the elevator is on the fifth floor and I am on the third, so I want it to come down to me". Much can be learnt about the design of user interfaces by considering this, apparently, simple interface. If you think about the elevator button problem you'll find that something so simple has hidden depths. How do people learn about elevator calling? What's the right amount of