快速计算得到最小和？
我有一个这样的数据
row1: x1 x2 x3... xn, y1,y2,...yn
row2: x2,x3,....xj, y4,y5,...ym
.....
row 1 million, x6,x2,x7...xk, y2,y3,...yl每一行，x和y的数量可以是一百万甚至更多。
每一行，一定数量的x或y可以具有相同的value.like行1和行2具有共同的x2。
我的目标是找出哪一行给我的x和y的和最小。例如，第一行的和是sum(x1+x2，..+xn+y1+y2+...yn)。
穷举方法可以工作，但会非常慢，因为将有一百万次操作，我相信有一些聪明的方法可以工作。
谢谢
更新：
实际上，上面问题来自于矩阵划分：，给出一个如下5x5的矩阵
1 2 3 4 5
2 3 4 5 6
2 3 4 5 8
9 1 2 3 5
1 5 2 5 6至少有五种方法可以将该矩阵划分为两个子矩阵，例如，
1 2 | 3 4 5
2 3 | 4 5 6
----+------
2 3 | 4 5 8
9 1 | 2 3 5
1 5 | 2 5 6我得到两个子矩阵
1 2
2 3和
4 5 8
2 3 5
2 5 6所以实际上1 2 2 3是我提到的x，4 5 8 2 3 5 2 5 6是我提到的y。所以每一行都是矩阵中的一种分裂。我不确定我是不是说清楚了？请添加评论。
回答 1
Stack Overflow用户
发布于 2012-05-01 20:16:38
从上面我看到的是x和y模式在两行上重叠，所以给出一个列表{x1，x2，...xn}和{y1，y2，..ym}
给定(1，n)中的i，j，k，l
和(1，m)中的o，p，q，r
第一行是：{ xi，xi+1，...，xj }{ yo，yo+1，...，yp }
第二行是：{ xk，xk+1，...，xl }{ yq，yq+1，...，yr }
因此，您真正需要找出的是行之间的差异并进行比较，并且仅求和，因为重叠部分(具有相同值的部分)将具有相同的总和。
关于这两份名单，你还有什么可以告诉我们的吗？排序好了吗？你知道x和y的列表是独立于行的吗？X列表中的值可以出现在y列表中吗？它们是以某种方式排序的吗？
知道这些东西会让你更快地弄清楚你需要什么。
如果不是，您将不得不遍历各行并确定重叠。
更新：
这假设我们只通过对角线分解，但你可以推广算法来做其他事情。
使用上面的例子，让我们看看我们是否可以工作，我正在按x和y集合对数字进行分组。
第1行：{1}{3 4 5 6 3 4 5 8 1 2 3 5 5 5 6}
行2：{1 2 2 3} {4 5 8 2 3 5 2 5 6}所以我们从第二列添加到x {2 3}，从第二行添加到{2}。
we removed from y {3 3 1 5} from the second column and {4 5 6} from the second row第3行：{1 2 3 2 3 4 2 3 4}{3 5 5 6}，因此我们将第三列中的x {3 4 4}和第三行中的{2 3}相加。
we removed from y {4 2 2 } from the thrid column and {5 8} from the third row请注意，我没有计算总和。只是与第1行的区别
因此，如果我们对除1之外的每一行进行泛化。(如果您不需要总和，则根本不计算第1行)
对于n×n矩阵M
延迟行1= 0；
对于r=2到r
对于i=1 to i <= r，以及j=1 to j
增量行r=增量行(r-1) + sum M(r，i) + sum M(j，r) - sum M(r，n-i) - sum M(n-j，r)
少于第1行的行将为负数。到目前为止，你可以只保留你所见过的最小的行增量，你就会知道哪个分解和是最小的。
这有意义吗？
https://stackoverflow.com/questions/10397106
复制相似问题
腾讯云开发者
