algorithm - 每行值的累计求和

Question

我有如下内容:

a = [1 11; 2 16; 3 9; 4 13; 5 8; 6 14];
b = a;
n = length(a);
Sum = [];

for i=1:1:n,
   Sum = b(i,2)+b(i+1:1:n,2)

end

b =

 1    11
 2    16
 3     9
 4    13
 5     8
 6    14

对于第一次迭代，我希望找到第二列中介于 19 和 25 之间的值的第一个组合。

Sum =

27
20
24
19
25

因为 20 是第一个组合(第 1 行和第 3 行)——我想在开始一个新矩阵时删除该数据或表示这是第一个组合(即通过创建第三列将 1 放在旁边)

下一步是将矩阵中的值与第 2 行的值相加:

Sum =
29
24
30

然后 2&5 将合并。

但是，我希望不仅可以组合成对，而且如果可能的话也可以组合多行。

有什么我忽略的东西可以简化这个问题吗？

Answer 1

我认为您不会将其简化太多。这是 knapsack problem 的变体，这是 NP 难的。使用的最佳算法可能取决于输入的大小。