[Top][All Lists]

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

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 <address@hidden> wrote:


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

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.

reply via email to

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