[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

'knapsack'-related algorithm

From: Przemek Klosowski
Subject: 'knapsack'-related algorithm
Date: Thu, 30 Jun 2011 16:18:17 -0400
User-agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv: Gecko/20110428 Fedora/3.1.10-1.fc15 Lightning/1.0b2 Thunderbird/3.1.10

This is partly a story about an interesting application of Octave in home remodeling, and partly a call to peer-review the code.

I was laying down a patterned hardwood floor and to minimize waste I wanted to select combinations of planks that would result in exactly dimensioned runs. It turns out that, given a random distribution of individual plank lengths, there are many combinations that result in any given length. Since I had around 75 planks, I calculated the lengths of all 30 million combinations of two, three and four planks, and selected and printed those that give the desired total length, using a brute force method.

I wonder if people here can suggest cleaner ways to write the algorithm I chose, and maybe come up with a cleaner, less wasteful algorithm---my method took a couple of minutes to calculate and 2GB of memory.

Specifically, I had 75 boards of lengths ranging from 25cm to 195cm,
and I needed 319.8 cm runs. I had my kid measure the boards to within 1mm and read it into an Octave variable 'a'. I then calculated the sums of all combinations of four boards---the 2 and 3 plank combinations are also included because I added two 'virtual' planks of length 0 to the set. I calculated only the 'upper triangular' combinations, of course:

m=length(a); z=1;

for i=1:m;
  for j=1:i-1;
    for k=1:j-1;
      for l=1:k-1;
      end ;
end ;

So, is there a vectorized way of writing this? Some sort of 'tensor' operation, I guess...

To get the final list, I need to find the entries that contain the interesting total length by sorting and selecting the relevant subset:

 xxx, yyy =..indices of the sorted data with the right length ...
for i=1:length(good);
  printf("%d %d %d %d %5.1f\n", igood(i),good(i));

It turns out that there were on the order of 2000 combinations of the desired length; this was more than I intuitively expected. I just printed the indices and length and just crossed out the combinations where one or more boards were previously used up--obviously if I chose, say, planks 23, 38, 48 and 61, other combinations using each of those boards become unavailable.

For a correct solution, I should have culled the list so that there would be no repetition, as mentioned above---perhaps even optimized the set for maximum number of combinations, because I suspect that e.g. sets that include two long planks block many combinations in which those long planks are combined with many short planks, so perhaps they should be avoided. As it is I just ran out of time to write that part of the program: wife started asking why I'm still at the computer :).

reply via email to

[Prev in Thread] Current Thread [Next in Thread]