Skip to main content

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.


Comments

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 2: http://pastebin.com/Dh6NWVaD
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;


}

Popular posts from this blog

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 last name …

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.0image 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), r, h, floor(m…

Importing an existing SSL key/certificate pair into a Java keystore

I'm writing this blog post in case anyone else has to Google that. In Java 6 keytool has been improved so that it now becomes possible to import an existing key and certificate (say one you generated outside of the Java world) into a keystore.

You need: Java 6 and openssl.

1. Suppose you have a certificate and key in PEM format. The key is named host.key and the certificate host.crt.

2. The first step is to convert them into a single PKCS12 file using the command: openssl pkcs12 -export -in host.crt -inkey host.key > host.p12. You will be asked for various passwords (the password to access the key (if set) and then the password for the PKCS12 file being created).

3. Then import the PKCS12 file into a keystore using the command: keytool -importkeystore -srckeystore host.p12 -destkeystore host.jks -srcstoretype pkcs12. You now have a keystore named host.jks containing the certificate/key you need.

For the sake of completeness here's the output of a full session I performe…