澄清答案...在SET中找到最大可能两个相等的和

Question

我需要澄清这个问题的答案,但我不能评论(不够代表)所以我问了一个新问题.希望没关系.

问题是这样的:

给定一个数组,你必须找到最大可能两个相等的和,你可以排除元素.

即1,2,3,4,6给定数组我们可以有最多两个相等的和6 + 2 = 4 + 3 + 1

即4,10,18,22,我们可以得到两个相等的和18 + 4 = 22

除了蛮力找到所有计算并检查两个可能的相等和之外,你的解决这个问题的方法是什么？

编辑1:数组元素的最大数量为N <= 50,每个元素最多可达1 <= K <= 1000

编辑2:总元素总和不能大于1000.

批准的答案说:

我建议使用DP来解决这个问题,而不是跟踪A,B(两组的大小),而是跟踪A + B,AB(两组的总和和差异).

然后,对于数组中的每个元素,尝试将其添加到A或B,或两者都不添加.

跟踪总和/差异的优点是您只需要跟踪每个差异的单个值,即您在此差异中看到的总和的最大值.

我不承诺的是:

如果这是子集求和问题,我可以用DP解决它,具有(N×P)的记忆矩阵,其中N是集合的大小,P是目标总和......

但我无法弄明白我应该如何跟踪A + B,AB(如批准答案的作者所述).哪个应该是memoization矩阵的维度？以及这有助于解决问题？

答案的作者很友好地提供了一个代码示例,但由于我不懂python(我知道java),因此很难对我进行处理.

Answer 1

我认为思考这个解决方案与单个子集问题的关系可能会误导您。这里我们关心的是可达到的最大总和，而且，我们需要在遍历时区分两个不相交的数字集。显然，跟踪特定组合的成本太高。

看看 A 组和 B 组之间的差异，我们可以说：

A - B = d
A = d + B

显然，当 时，我们希望得到最高的总和d = 0。我们怎么知道这个总数？它是(A + B) / 2！

对于动态程序中的转换，我们想知道是否将当前元素放置在 A、B 中更好，还是两者都不放置。这是这样实现的：

e <- current element
d <- difference between A and B

(1) add e to A -> d + e

why? 
A = d + B
(A + e) = d + e + B

(2) add e to B -> d - e

why? 
A = d + B
A = d - e + (B + e)

(3) don't use e -> that's simply
  what we already have stored for d

让我们看一下 Peter de Rivas 的转换代码：

A - B = d
A = d + B

最后，我们存储了 d = 0 时看到的最高 A + B，其中 A 和 B 中的元素形成不相交的集合。返回 (A + B) / 2。