Error Bounds and the Applicability of the Greedy Solution to the Coin-Changing Problem

Necessary and sufficient conditions have been given that characterize the data for which a greedy algorithm solves the coin-changing problem. In this paper we study the problem of maximum percentage error when the greedy solution does not work. We also generalize a result of Johnson and Kernighan to the case for which each coin is of different weight.