# Max sum of array elements with condition

2 visualizzazioni (ultimi 30 giorni)
Blaz il 5 Dic 2013
Risposto: Roger Stafford il 5 Dic 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 CommentiMostra NessunoNascondi Nessuno
Jos (10584) il 5 Dic 2013
15 consecutive elements, or a random combination of 15 elements?
Blaz il 5 Dic 2013
random

Accedi per commentare.

### 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;
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!
##### 0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

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
##### 0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

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 CommentiMostra NessunoNascondi Nessuno
sixwwwwww il 5 Dic 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?
Blaz il 5 Dic 2013
just the maximum one

Accedi per commentare.

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;
end
end
end
Then mx is the maximum encountered in the N steps and px indicates the corresponding set of rows.
##### 0 CommentiMostra -2 commenti meno recentiNascondi -2 commenti meno recenti

Accedi per commentare.

### Categorie

Scopri di più su Logical 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