Let $D$ be set of denominations and $m$ the largest element of $D$. We say that $c$ is a counterexample if the greedy algorithm gives an answer different from the optimal one.
Now, apparently, if for a given set $D$, the greedy algorithm does not return an optimal solution, then the smallest $c$ will be smaller than $2m-1$.
Is this really true? How can we prove it? If not, is there a relatively small range to look for the smallest counterexample?
Best Answer
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.