________________________________ From: Bernie Cosell <bernie@fantasyfarm.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Friday, November 14, 2008 1:21:43 PM Subject: [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 <-- _______________________________________________ Ignoring the "intuitive" and "unintuitive" distinction, considering instead the unconstrained optimization, I would use dynamic programming. If an optimum N cent solution consists of more than one coin, then for any partition of these coins into N1 cents and N2 cents, N = N1 + N2, the N1 and N2 cent piles are each also optimum. So solve the problem for N =1, 2, 3, 4, ... in succession. (Minimum Number of Coins)(N) = min( (Minimum Number of Coins)(K) + (Minimum Number of Coins)(N-K), K = 1..N-1). This fails only when the optimum is a single coin, but those cases are clear; they are the single coin values. Gene