Algorithm for change-making problem

  • Thread starter Appledave
  • Start date
  • #1
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.
 

Answers and Replies

Related Threads on Algorithm for change-making problem

  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
11
Views
4K
Replies
3
Views
688
  • Last Post
Replies
4
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
3
Views
11K
  • Last Post
Replies
2
Views
2K
Replies
1
Views
935
  • Last Post
Replies
6
Views
774
Replies
3
Views
896
Top