I'm not sure that this is the right place for this post, but I couldn't find a better.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Greedy algorithm

**Physics Forums | Science Articles, Homework Help, Discussion**