algorithm - 两个数组中元素的总和相同

Question

我有两个长度相同的整数数组 v1 和 v2。我想找到 v1 元素的最大子集，其总和与 v2 中相应元素的总和相同。例如，让

v1 = [1 2 3 1] 
v2 = [2 3 1 2]

两个数组中第二个、第三个和第四个元素的总和是 6，所以这就是我要查找的子集。

有没有办法计算这个？

非常感谢。切萨雷

Answer 1

计算增量，问题简化为 subset sum problem .换句话说，创建第三个数组，其中每个元素是两个输入数组中相应元素之间的差值。

例如，给定输入数组 v1 和 v2，创建包含差异的第三个数组 v3:

       0  1  2  3   <-- index into the array
v1 = [ 1  2  3  1] 
v2 = [ 2  3  1  2]
v3 = [-1 -1  2 -1]

然后 v3 中添加到 0 的任何子集都是一个解决方案。在此示例中，解决方案由索引集表示:{0,1,2}、{0,2,3} 和 {1 ,2,3}.