help-octave
[Top][All Lists]

## Re: 'knapsack'-related algorithm

 From: Moo Subject: Re: 'knapsack'-related algorithm Date: Fri, 1 Jul 2011 09:14:27 -0600

On Thu, Jun 30, 2011 at 2:18 PM, Przemek Klosowski wrote:

(snip)

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

I have no expertise in combinatorial optimization, so I'll just help with your brute force method.

I think the nchoosek() function is what you want.  If you give it a vector as the first argument (e.g., nchoosek(v,k)), it produces an array where each row is a combination of k elements of v.  I don't believe it repeats.  So, to implement...

% plank lengths
n = 75;
a = rand(n,1)

% Produce all combinations at once.
combs = nchoosek(1:n,4);

% Replace the indices with actual plank lengths, then sum along each row.
lengths = sum(a(combs),2)

Be sure to rename your vector of summed plank lengths from 'sum' to something else to avoid errors, though, since sum() is a core function in Octave.

After this you can do basically the same analysis; choose which rows gave the desired length, then go to the corresponding row in the combs() array which gives you the plank numbers.