This is one of those NP problems which are usually tractable, this is an interesting article from American Scientist.

One greedy algorithm assuming you have a standard length of skirting board and varying wall lengths. The steps are

1. Find the "odd" lengths, that is the remaining length on each wall after using the standard lengths.
2. Sort the remainders by length, longest first.
3. Select the longest and assign it to the shortest length of skirting board it will fit in, if it can't be fitted to an existing board then use a new one..
4. Repeat previous step until there are no remaining lengths

An example

skirting length: 5
wall lengths: 24 16 21 4 3 12
remainders: 4 1 1 4 3 2
sorted rem: 4 4 3 2 1 1

Skirting 1: 4 ( available 1 )
sorted rem: 4 3 2 1 1

Skirting 1: 4 ( available 1 )
Skirting 2: 4 ( available 1 )
sorted rem: 3 2 1 1

Skirting 1: 4 ( available 1 )
Skirting 2: 4 ( available 1 )
Skirting 3: 3 ( available 2 )
sorted rem: 2 1 1

Skirting 1: 4 ( available 1 )
Skirting 2: 4 ( available 1 )
Skirting 3: 3 2 ( available 0 )
sorted rem: 1 1

Skirting 1: 4 1 ( available 0 )
Skirting 2: 4 ( available 1 )
Skirting 3: 3 2 ( available 0 )
sorted rem: 1

Skirting 1: 4 1 ( available 0 )
Skirting 2: 4 1 ( available 0 )
Skirting 3: 3 2 ( available 0 )
[download]

Ah! I had overlooked second part of your third point, i.e. that the longest wall should be matched to the shortest remaining bit of skirting.

Thanks,

loris

---

"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)

Yes, greed can be hard to wrap your mind around;) Good luck with the DIY.

See Cutting stock problem

It wouldn't be a half bad idea to try and write a brute force solution and, if (as you might expect) it doesn't run in reasonable time or you run into some other implementation issue, you can then legitimize your somewhat off topic node by posting some code. ;)

There is plenty of precedent for nodes related to using Perl for solving tricky problems of this sort. An interesting example is Challenge: 2D random layout of variable-sized rectangular units..

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 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.

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;
[download]

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.

I'm no builder, but I would assume that bits of skirting board come in standard lengths? And I would also assume that you then just cut them to suit?

So given that you've already measured all your walls, isn't it simply a matter of taking the sum of all these lengths, and then dividing that by the standard length of an off-the-shelf skirting board?

Or, as I strongly suspect, am I missing something that makes it somewhat more complicated?

Cheers,
Darren

I'm also no builder and your approach would work. But the problem is to do each bit of wall with only one piece of skirting board (apart from the walls longer that the off-the-shelf length, of course). With your method, I might have to use half a dozen leftover pieces on the last bit of wall. I could of course just put a cupboard in front of it ...

loris

---

"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)

You also have the problem of mitres left or right, inside or outside, if you get it right first time it can save a lot of extra work not having to cut extra mitres and also save the loss that each cut takes from the skirting length.

It may sound trivial but if you have large skirtings in my house for example the boards are 14 inches wide with lots of ogees and detailing and now have to be specially made. Being economical with cutting and length can save a lot of money in the long run.

I have to admit the last time I did a room I drew it out on graph paper first, then cut paper strips to the length of the skirting and fitted them in place on the drawing first.
Testing by cutting paper was a lot easier and cheaper than cutting full boards. The skirting lengths could then be matched to the appropriate board length.