Max sum of array elements with condition

2 visualizzazioni (ultimi 30 giorni)
Blaz il 5 Dic 2013
Risposto: Roger Stafford il 5 Dic 2013
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

Risposte (4)

sixwwwwww il 5 Dic 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;
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;
i hope it helps. Good luck!

Jos (10584)
Jos (10584) il 5 Dic 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 il 5 Dic 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 Commenti
Blaz il 5 Dic 2013
just the maximum one

Accedi per commentare.

Roger Stafford
Roger Stafford il 5 Dic 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;
Then mx is the maximum encountered in the N steps and px indicates the corresponding set of rows.


Scopri di più su Resizing and Reshaping Matrices in Help Center e File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by