Clear Filters
Clear Filters

Max sum of array elements with condition

9 views (last 30 days)
Blaz
Blaz on 5 Dec 2013
Answered: Roger Stafford on 5 Dec 2013
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
  2 Comments
Jos (10584)
Jos (10584) on 5 Dec 2013
15 consecutive elements, or a random combination of 15 elements?

Sign in to comment.

Answers (4)

sixwwwwww
sixwwwwww on 5 Dec 2013
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!

Jos (10584)
Jos (10584) on 5 Dec 2013
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

Blaz
Blaz on 5 Dec 2013
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
  2 Comments
sixwwwwww
sixwwwwww on 5 Dec 2013
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?

Sign in to comment.


Roger Stafford
Roger Stafford on 5 Dec 2013
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.

Categories

Find more on Creating and Concatenating Matrices in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!