- #1
- 2,845
- 0
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?
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?