No such thing as a small change  
PerlMonks 
"The Skirting Board Problem"by loris (Hermit) 
on Jan 22, 2008 at 09:01 UTC ( #663523=perlquestion: print w/replies, xml )  Need Help?? 
loris has asked for the
wisdom of the Perl Monks concerning the following question:
Dear DIYMonks, The following is a bit OT, but bear with me please. I need to fit some skirting boards in my house. So I have measured out all the bits of wall and now need to know many pieces of skirting board I need to buy, so that the amount left over once I have completed the work is minimized. This is obviously an example of the general problem of having a set of numbers and trying to find the minimum number of groups, the sum of whose members does not exceed a certain value. I am currently a bit stuck regarding an elegant approach to this problem. I can conceive of a sort of brute force approach of just trying out a whole bunch of combinations, but there must be a more intelligent way. I assume that the best way could depend of the distribution of the numbers, e.g. whether I have and even spread or, say, large numbers and small numbers with not much in between. On the one hand I am sure some of you can tell me what the proper name of this problem is, so that I can google for information about it more easily. On the other hand, I am sure that some of you have good ideas about how to go about solving the problem in a perly way. Thanks, Update: This is homework, but only in the literal, DIYsense. "It took Loris ten minutes to eat a satsuma . . . twenty minutes to get from one end of his branch to the other . . . and an hour to scratch his bottom. But Slow Loris didn't care. He had a secret . . ." (from "Slow Loris" by Alexis Deacon)
Back to
Seekers of Perl Wisdom

