### 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\]

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.

*If you enjoyed this blog post, you might enjoy my travel book for people interested in science and technology: The Geek Atlas. Signed copies of The Geek Atlas are available.*

<$BlogCommentBody$>

Create a Link

<< Home