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

Greedy algorithm

  1. Oct 4, 2006 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I'm not sure that this is the right place for this post, but I couldn't find a better.

    Many years ago I considered the problem of making change with (say) quarters, dimes, nickels, and pennies. I tried to prove to myself that what I now call the greedy algorithm (pick the most valuable coin that doesn't take you over your limit) always made optimal change -- that no solutions with fewer coins existed. At the time I wasn't able to find a proof of the specific case {25, 10, 5, 1} but I could see that the general result failed -- consider {5, 4, 1} to make a total of 8 cents. The greedy algorithm gives (5, 1, 1, 1) but (4, 4) is better.

    I was wondering if there's a good characterization of what combination of coin values make the greedy algorithm always optimal. Back then I could see that being in a geometric series was a sufficient, but unnecessary, condition. Briefly reconsidering the problem, it seems that the greedy algorithm should be optimal for superincreasing sequences -- but is this necessary for optimality? Any thoughts, counterexamples, or reading/references?
     
  2. jcsd
  3. Oct 4, 2006 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is certainly a classical problem. A quick search turns up this:

    http://mathforum.org/wagon/spring04/p1009.html

    (but I can't seem to follow the link contained in it. I don't think you could get the text easily from there anyways)

    which makes it sound like a necessary and sufficient condition won't be simple to write. I know there are some nice, simple, sufficient conditions, but I can't remember the usual one, and I think my only hard reference is at work.


    edit: I think this is the paper on it. (You can grab it from the "cached: ... PDF" link in the top-right corner) It doesn't seem terribly clear, but maybe I'm just tired. :smile:
     
    Last edited: Oct 4, 2006
  4. Oct 4, 2006 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Thanks a bunch, that's exactly what I was hoping for I'll read through it and see how much I get. I appreciate it!
     
  5. Oct 4, 2006 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Well, I read the paper. It shows that it can be decided in polynomial time (O(n^2)) if a certain combination of coin values can always be solved optimally with the greedy algorithm, even though determining the least number of coins needed for a given set of coin values and total x is NP-hard.

    Also, I was able to find a counterexample to my 'conjecture' above. Not all superincreasing sequences are solved optimally by the greedy algorithm; consider coins {2001, 1000, 1} and total 3000. I'll see if I can find the least superincreasing counterexample now -- clearly, it has exactly 3 coins.

    Edit: I think it's {6, 4, 1} with a total of 8.
     
    Last edited: Oct 4, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Greedy algorithm
  1. No fastest algorithm (Replies: 10)

  2. Search algorithm (Replies: 14)

  3. Math algorithm (Replies: 5)

  4. Nesting Algorithm (Replies: 1)

Loading...