# Algorithm for change-making problem

1. Nov 4, 2011

### Appledave

Ok, so I found this article that presents an algorithm for deciding whether or not a set of coins allows for use of a greedy algorithm when making change:

http://ecommons.cornell.edu/bitstream/1813/6219/1/94-1433.pdf

But I'm not quite sure if I've understood it. The way I see it you do the following:

-choose i and j
-compute G(ci-1 -1)
-from G(ci-1 -1), find M(w)
-from M(w) find w
-compute G(w)
-if |M(w)| < |G(w)| there is a counterexample and the coin set does not allow for a
greedy algorithm
-repeat for different combinations of i and j until you find a counterexample or until all
combinations have been tried, in which case the coin set allows for use of a greedy
algorithm