Optimal Bounds for the Change-Making Problem

Abstract

The change-making problem is the problem of representing a given value with the fewest coins possible. We investigate the problem of determining whether the greedy algorithm produces an optimal representation of all amounts for a given set of coin denominations 1 = c_1 < c_2 < ... < c_m. Chang and Gill show that if the greedy algorithm is not always optimal, then there exists a counterexample x in the range

c_3 <= x < (c_m(c_m c_m-1 + c_m - 3c_m-1)) \ (c_m - c_m-1).

To test for the existence of such a counterexample, Chang and Gill propose computing and comparing the greedy and optimal representations of all x in this range. In this paper we show that if a counterexample exists, then the smallest one lies in the range c_3 + 1 < x < c_m + c_m-1, and these bounds are tight. Moreover, we give a simple test for the existence of a counterexample that does not require the calculation of optimal representations.

In addition, we give a complete characterization of three-coin systems and an efficient algorithm for all systems with a fixed number of coins. Finally, we show that a related problem is coNP-complete.