Max sum of array elements with condition

4 次查看（过去 30 天）
Blaz
Blaz 2013-12-5
回答： Roger Stafford 2013-12-5
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

请先登录，再回答此问题。

回答（4 个）

sixwwwwww
sixwwwwww 2013-12-5
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) 2013-12-5
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 2013-12-5
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 个评论
sixwwwwww
sixwwwwww 2013-12-5
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?

请先登录，再进行评论。

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

类别

在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by