Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm for change-making problem

  1. Nov 4, 2011 #1
    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.
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted