[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* **<=**