|No such thing as a small change|
"The Skirting Board Problem"by loris (Hermit)
|on Jan 22, 2008 at 09:01 UTC||Need Help??|
loris has asked for the
wisdom of the Perl Monks concerning the following question:
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.
Update: This is homework, but only in the literal, DIY-sense.
"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)