3

我们有一个 MxN 矩阵和一个约束cstrn = 100;。

约束是列元素的汇总限制（每列）：

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

对于给定的示例，如下所示：

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

我想找到满足此约束的每列元素的最大数量。

我如何将每个列元素与同一列中的其他元素进行汇总，并找到哪些总和组合使用每列的最大元素数？

在给定的示例解决方案中是：

   4  3  5  2  5

在哪里

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

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

先感谢您。

4

3 回答 3

4

由于将小元素放入总和总是更容易，因此您可以执行 a sort，然后是累积总和：

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

现在您可以轻松识别出您跨越阈值的元素cnstrn（感谢@sevenless）！

out = sum(cs <= cnstrn)

out =
     4     3     5     2     5
于 2012-12-05T17:15:52.770 回答
3

我想补充一下乔纳斯的回答，你可以通过输出一个逻辑矩阵的方式来施加你的约束，然后对该矩阵的 1 和 0 求和，如下所示：

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)

给出输出：

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
于 2012-12-05T17:22:37.903 回答
1

这是一个逻辑，在移动设备上所以不能给出代码。

看一下这个。转到一列，按升序对其进行排序，循环求和，当命中 <=100 时中断。拿到柜台。返回原始列，获取与您刚刚总结的元素匹配的元素的索引 :-)

于 2012-12-05T17:18:06.310 回答