Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
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??


in reply to "The Skirting Board Problem"

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 bin-packing 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 NP-complete. 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: First-fit decreasing would look like this (untested):
my $B = ...; # bucket size my @items = qw[ ... ]; # items my @bins; my @binsizes; ITEM: for my $item (sort { $b <=> $a } @items) { for my $bin (0 .. $#binsizes) { if ($binsizes[$bin] + $item <= $B) { push @{ $bins[$bin] }, $item; $binsizes[$bin] += $item; next ITEM; } } push @bins, [$item]; push @binsizes, $item; } print "[@$_]\n" for @bins;

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 brute-force method will not take too long. But it might take longer to code the brute-force 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 first-fit 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


Comment on Re: "The Skirting Board Problem"
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://663596]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (12)
As of 2015-07-29 22:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (269 votes), past polls