1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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




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...