# Change-making problem - counterexample for greedy algorithm

Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one.

I found statement that if for given set greedy algorithm is non-optimal, the smallest c will be smaller than 2m-1.

The question is if it's really true and how to prove it? If not, is there a relatively small range to look for the smallest counterexample?

-
How do you define the optimal solution? What objective function do you optimize? –  Yury Dec 1 '12 at 3:50
@Yury: You want to minimize the number of coins used to make up the given amound. –  Brian M. Scott Dec 1 '12 at 7:24
I think you need some assumptions, e.g. for coins $\{2-\sqrt{2}, 1, \sqrt{2}\}$, the first natural number for which the greedy algorithm doesn't work is $3 > 2\sqrt{2}$. If you are talking about coins $\in \mathbb{N}$, then I remember something similar, but I can't recollect the source. The articles mentioned by Hendrik look promising, however ,it was not there where I saw it. –  dtldarek Dec 1 '12 at 11:12
add comment

## 2 Answers

The paper "Optimal Bounds for the Change-Making Problem" (by Kozen and Zaks, TCS 1994) gives a bound of $x < c_M + c_{m-1}$ where $x$ is the counter example and $c_m$ and $c_{m-1}$ are the largest and second largest coin. They claim the bound is optimal. (I just browsed the paper, and I did not take the time to understand whether this automatically means you cannout expres it in the largest coin value)

Jeffrey Shallit (famous for his paper "What this country needs is an 18c piece") in 1998 posted a bibliography on the subject: mathforum. Shallit adds "... it is a problem in which it is notoriously easy to make wrong conclusions -- some of them have even been published".

Good luck with your investigations.

-
add comment

I recently came up with 1 solution that seemed to show if the given 2 conditions are satisfied, the greedy algorithm would yield the optimal solution.

a) The G.C.D (All the denominations except 1) = 2nd Smallest denomination.

b) The sum of any 2 consecutive denominations must be lesser than the 3rd consecutive denomination.

For eg. $c_2 + c_3 < c_4$.

(Where $c_1 = 1; c_2, c_3, c_4$ are coin denominations in ascending order).

I understand this is not a complete solution. However, I believe that if these 2 conditions are met, the greedy algorithm will yield the optimal solution.

-
Duplicate answer. As there, this would be more useful if accompanied by a proof. –  robjohn Mar 6 '13 at 9:56
add comment