Just another Perl shrine  
PerlMonks 
Re: "The Skirting Board Problem"by blokhead (Monsignor) 
on Jan 22, 2008 at 15:06 UTC ( #663596=note: print w/ replies, xml )  Need Help?? 
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.What you describe is the binpacking problem. Each length of board represents a bin and the lengths to be cut for each wall represent the set of items to be packed into the fewest number of bins. 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.Not likely, since the problem is NPcomplete. On the bright side, there are many simple approximations for this problem which give a guaranteed approximation ratio^{*}. The wikipedia article mentions a few which give quite good ratios (11/9). They use very simple rules. For example: Firstfit decreasing would look like this (untested):
Other places to look include Algorithm::Bucketizer or Algorithm::BinPack, but I don't know which heuristic algorithm they use under the hood. BTW, it's likely you have few enough items (with small values) so that the bruteforce method will not take too long. But it might take longer to code the bruteforce search than to execute it (or install your skirting boards)! Appendix/Update: A guaranteed approximation ratio of 11/9 means that if the optimal solution to a problem instance uses N bins, then the approximation/heuristic algorithm is guaranteed to return a solution for that instance that uses no more than (11/9)*N bins. (Note that I am ignoring the extra +1 in the guarantee for firstfit decreasing  it will give you a solution that uses at most (11/9)*N+1 bins) Also note that this ratio is tight, which means that there are indeed pathological cases where the algorithm gives solutions that really are a (11/9) factor worse than optimal. However, chances are that most inputs will not yield this worst case  and at least there is a known bound about how bad things can really get. blokhead
In Section
Seekers of Perl Wisdom

