[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:1.9.2.17) 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:
tic;
m=length(a); z=1;
sz=m*(m-1)*(m-2)*(m-3);ind=zeros(sz,4);sum=zeros(sz);
for i=1:m;
for j=1:i-1;
for k=1:j-1;
for l=1:k-1;
ind(z,1:4)=[i,j,k,l];
sum(z)=a(i)+a(j)+a(k)+a(l);
z++;
end ;
end;
end;
end ;
toc;
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:
[sorted,is]=sort(sum)
xxx, yyy =..indices of the sorted data with the right length ...
good=sorted(xxx:yyy)
igood=ind(is(xxx:yyy),:)
for i=1:length(good);
printf("%d %d %d %d %5.1f\n", igood(i),good(i));
end
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 :).
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- 'knapsack'-related algorithm,
Przemek Klosowski <=