Max sum of array elements with condition

Hello,

If someone would be kind enough to help me with my problem I'd be most grateful.

I have matrix size nx2 (n>100) and I'd like to get maximum sum of 15 elements in first column, but in the same time the sum of same row elements in second column should not exceed 100

[Jos (10584)]

15 consecutive elements, or a random combination of 15 elements?

[Blaz]

random

Answer 1

[sixwwwwww]

you can do something like this:

Matrix{1,1} = {'start index'};
Matrix{1,2} = {'end index'};
Matrix{1,3} = {'sum'};
a = randi(10, 100);
count = 2;
for i = 1:size(a, 1)
    if i < size(a, 1) - 14
        for j = 0:14
            if sum(a(i:i+j, 2)) < 100
                Matrix{count, 1} = i;
                Matrix{count, 2} = i + j;
                Matrix{count, 3} = sum(a(i:i+j, 2));
                count = count + 1;
            end
        end
    else
        ind = size(a, 1) - i;
        for j = 0:ind
            if sum(a(i:i + j, 2)) < 100
                Matrix{count, 1} = i;
                Matrix{count, 2} = i + j;
                Matrix{count, 3} = sum(a(i:i + j, 2));
                count = count + 1;
            end
        end
    end
end

i hope it helps. Good luck!

Answer 2

[Jos (10584)]

For consecutive elements you can use cumsum, like here:

% example data
  M = ceil(10*rand(10,2)) % much longer in your case
  k = 3 ; % 15 in your case
  max2 = 20 ; % 100 in your case

% engine  
  CM = cumsum(M,1) 
  CMn = CM(k:end,:) - [zeros(1,size(M,2)) ; CM(1:end-k,:)] % consecutive sum of n elements
  CMn(CMn(:,2) > max2,1) = -Inf % implement restriction
  [maxSumn, idx] = max(CMn(:,1)) % what is the maximum
  result = M(idx:idx+n-1,:) % get the rows of M

Answer 3

[Blaz]

Thank you guys for quick answer, but that's not exactly what I need. I do not need max sum of 15 consecutive elements, but max sum of 15 elements from whole array

[sixwwwwww]

how may combinations you like to try for this process. since you have column of 100 then there will be alot alot combinations of random number which could be summed. SO can you specify how many sum you need?

[Blaz]

just the maximum one

Answer 4

[Roger Stafford]

You have asked a rather difficult question, Blaz. If the brute force method of trying every possible combination of 15 elements from among over 100 is used, the number of those inspections would have to be in excess of 100!/15!/85! = 2.5334e17, so that is rather impractical.

One heuristic possibility comes to mind. You can set up a process that at each step selects a random combination of 15 rows from among the over 100 in your matrix and tests the second column elements for having a sum not in excess of 100. If that is true, then the sum of the corresponding 15 in the first column is found. Whenever the latter surpasses the maximum so far encountered, it is to replace that maximum. You are very unlikely to find the true maximum in this way but you will probably get one which is very high up the list of sums if you repeat this for a large number of steps. You can use the randperm(n,15) command to select a random 15 out of n rows for performing a test.

Let M be your n x 2 matrix.

 N = 1e9; % Choose a very, very large number of steps
 mx = -inf;
 for k = 1:N
   p = randperm(n,15);
   if sum(M(p),2) <= 100
     s = sum(M(p),1);
     if s > mx
       mx = s;
       px = p;
     end
   end
 end

Then mx is the maximum encountered in the N steps and px indicates the corresponding set of rows.