comment on

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

Find the "odd" lengths, that is the remaining length on each wall after using the standard lengths.
Sort the remainders by length, longest first.
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..
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]

In reply to Re: "The Skirting Board Problem" by hipowls
in thread "The Skirting Board Problem" by loris

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Problems? Is your data what you think it is?
	PerlMonks