- #1
Appledave
- 14
- 0
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
does this sound about right?
Copious amounts of thanks in advance :) I realize asking people to read the article is a bit much.
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
does this sound about right?
Copious amounts of thanks in advance :) I realize asking people to read the article is a bit much.