Matlab: sum column elements with restrictions

Question

We have a MxN matrix and a constrain cstrn = 100;.

The constrain is the summarize limit of column's elements (per column):

sum(matrix(:,:))<=cstrn.

For a given example as the following:

Columns 1 to 5:
  15  18  -5 22 19
  50  98 -15 39 -8
  70 -15  80 45 38
  31  52   9 80 72
  -2  63  52 71  6
   7  99  32 58 41 

I want to find the max number of element per column who fulfill this constrain.

How can i summarize every column element with the others elements in same column and find which sum combinations uses the max number of elements per column?

In the given example solution is:

   4  3  5  2  5

where

column 1: 15 + 50 + 31 +7 +(-2)

column 2: 18 +(-15) + 52 or 63 etc.

Thank you in advance.

Answer 1

Since it is always easier to fit small elements into a sum, you can do a sort, followed by the cumulative sum:

m= [
  15  18  -5 22 19
  50  98 -15 39 -8
  70 -15  80 45 38
  31  52   9 80 72
  -2  63  52 71  6
   7  99  32 58 41]; 

cs = cumsum(sort(m))
cs =
    -2   -15   -15    22    -8
     5     3   -20    61    -2
    20    55   -11   106    17
    51   118    21   164    55
   101   216    73   235    96
   171   315   153   315   168

Now you easily identify at which element you cross the threshold cnstrn (thanks, @sevenless)!

out = sum(cs <= cnstrn)

out =
     4     3     5     2     5

Answer 2

I'd add to Jonas's answer, that you can impose your constraint in a way that outputs a logical matrix then sum over the 1's and 0's of that matrix like so:

cstrn = 100
m= [
  15  18  -5 22 19
  50  98 -15 39 -8
  70 -15  80 45 38
  31  52   9 80 72
  -2  63  52 71  6
   7  99  32 58 41]; 

val_matrix = cumsum(sort(m))
logical_matrix = val_matrix<=cstrn
output = sum(logical_matrix)

Giving output:

cstrn =

   100


val_matrix =

    -2   -15   -15    22    -8
     5     3   -20    61    -2
    20    55   -11   106    17
    51   118    21   164    55
   101   216    73   235    96
   171   315   153   315   168


logical_matrix =

     1     1     1     1     1
     1     1     1     1     1
     1     1     1     0     1
     1     0     1     0     1
     0     0     1     0     1
     0     0     0     0     0


output =

     4     3     5     2     5

Answer 3

Here is a logic, on mobile so can't give a code.

Check this out. Go to a column, sort it ascending order, loop to sum, break when hits <=100. Get counter. Refer back to original column, get the indices of elements matching the elements you just summed up :-)