[math-fun] First fit optimal collections
I was recently playing around with a little programming puzzle to find "optimal" coin-amounts to be able to make any amount up to a dollar. The description distinguished between "intuitive" and "nonintuitive" sets, the former being ones in which first-fit gets you the minimum # of coins needs [and so penny-nickel-quarter is intuitive, while penny-dime- quarter isn't, because .30 is better done with three dimes than a quarter and five pennies]. I can write the program fairly easily to try coin- sets and see what the average number of coins it takes is to make up every amount from .01 to 1.00. BUT: the intuitive requirement has me a bit puzzled. Assuming I do some kind of brute-force combinatorial program to try every combination of two-coin-sets, three-coin-sets, etc, I'm not sure what to do next. Doing a quick first-fit on the 100 amounts to get the average # of coins required is simple enough, but is there some way to look at a collection of coin-sizes and tell if they form an "intuitive" set or not? If not, it looks like the search is going to be VERY hard -- basically you'll have to end up doing pretty much a full tree walk of EVERY possible combination (you can do a bunch of tree-pruning to keep the size of the search manageable, but now this is no longer a 15-minute little programming hack but is starting to sound like a real program..:o)) /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
check out this mathematica "demonstration" from stan wagon: http://demonstrations.wolfram.com/OptimalityOfGreedyChangeMaking/ he lists a reference there, in case you don't have mathematica. bob ---
I was recently playing around with a little programming puzzle to find "optimal" coin-amounts to be able to make any amount up to a dollar. The description distinguished between "intuitive" and "nonintuitive" sets, the former being ones in which first-fit gets you the minimum # of coins needs [and so penny-nickel-quarter is intuitive, while penny-dime- quarter isn't, because .30 is better done with three dimes than a quarter and five pennies]. I can write the program fairly easily to try coin- sets and see what the average number of coins it takes is to make up every amount from .01 to 1.00. BUT: the intuitive requirement has me a bit puzzled.
Assuming I do some kind of brute-force combinatorial program to try every combination of two-coin-sets, three-coin-sets, etc, I'm not sure what to do next. Doing a quick first-fit on the 100 amounts to get the average # of coins required is simple enough, but is there some way to look at a collection of coin-sizes and tell if they form an "intuitive" set or not? If not, it looks like the search is going to be VERY hard -- basically you'll have to end up doing pretty much a full tree walk of EVERY possible combination (you can do a bunch of tree-pruning to keep the size of the search manageable, but now this is no longer a 15-minute little programming hack but is starting to sound like a real program..:o))
/Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let me recommend Jeff Shallit's article "What this country needs is an 18-cent piece," Math. Intelligencer 25#2 (Spring 2003), and available from his website at http://www.cs.uwaterloo.ca/~shallit/papers.html --Michael On Fri, Nov 14, 2008 at 4:21 PM, Bernie Cosell <bernie@fantasyfarm.com>wrote:
I was recently playing around with a little programming puzzle to find "optimal" coin-amounts to be able to make any amount up to a dollar. The description distinguished between "intuitive" and "nonintuitive" sets, the former being ones in which first-fit gets you the minimum # of coins needs [and so penny-nickel-quarter is intuitive, while penny-dime- quarter isn't, because .30 is better done with three dimes than a quarter and five pennies]. I can write the program fairly easily to try coin- sets and see what the average number of coins it takes is to make up every amount from .01 to 1.00. BUT: the intuitive requirement has me a bit puzzled.
Assuming I do some kind of brute-force combinatorial program to try every combination of two-coin-sets, three-coin-sets, etc, I'm not sure what to do next. Doing a quick first-fit on the 100 amounts to get the average # of coins required is simple enough, but is there some way to look at a collection of coin-sizes and tell if they form an "intuitive" set or not? If not, it looks like the search is going to be VERY hard -- basically you'll have to end up doing pretty much a full tree walk of EVERY possible combination (you can do a bunch of tree-pruning to keep the size of the search manageable, but now this is no longer a 15-minute little programming hack but is starting to sound like a real program..:o))
/Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
participants (3)
-
Bernie Cosell -
Michael Kleber -
rjbaillie＠frii.com