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

本文介绍了澄清答案...在SET中找到最大可能的两个相等和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我需要澄清此问题，但我无法发表评论（代表人数不足），所以我问一个新问题。希望没问题。

问题是这样的：

给出一个数组，您必须找到最大可能的两个相等和，您可以排除元素。

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

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

除了蛮力强制查找所有计算并检查两个可能的相等总和之外，您将采用什么方法来解决此问题？ / p>

编辑1：数组元素的最大数目为N <== 50，每个元素可以为，直到1 <== K <= 1000

编辑2：元素总和不能大于1000。

已批准的答案说：

我建议使用DP解决此问题，而不是跟踪A，B（两组的大小），您改为跟踪A + B，AB（t的总和与之差

然后为数组中的每个元素，尝试将其添加到A或B或都不添加到中。

跟踪总和/差的优点是，您只需要跟踪每个差额的单个值，即您看到的总和中最大的值

我不理解的是：

如果这是我可以用DP解决的子集总和问题，其存储矩阵为（N x P），其中N是集合的大小，P是目标总和...

但是我无法弄清楚我应该如何跟踪A + B，AB（正如批准答案的作者所说）。记忆矩阵的维数应该是多少？

答案的作者很友好，可以提供一个代码示例，但是我很难理解，因为我不知道python（我知道Java）。

解决方案

我认为思考此解决方案与单子集问题的关系可能会误导您。在这里，我们关注的是最大可实现的总和，此外，我们在遍历时需要区分两组不相交的数字。显然，跟踪特定组合会太昂贵。

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

A-B = d A = d + B

很显然，当 d = 0 时，我们希望获得最高的总和。我们怎么知道那笔款项？ （A + B）/ 2 ！

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

e<-当前元素d<-A与B之间的差 （1）将e添加到A-> d + e 为什么？ A = d + B （A + e）= d + e + B （2）在B上加上e-> d-e 为什么？ A = d + B A = d-e +（B + e） （3）不使用e->简直就是我们已经为d

存储的

让我们看看Peter de Rivas的代码进行过渡：

＃更新地图的副本，因此＃我们可以引用以前的值＃，同时分配新值 D2 = D.copy（） ＃d是A-B ＃s是A + B $ d，s在D.items（）中的b $ b： ＃包含元素＃的新总和＃我们还不确定＃是否会在A或B s2 = s + a ＃d2将依次采用这里的每个值＃，一旦d-a（将B加a），＃和一次d + a（在A上加上a）[b，d + a]中d2的： ＃主要转换：＃两个新的区别，＃（da）和（d + a）作为＃的键＃我们的地图获得了迄今为止最高的金额＃，或者（1）＃新金额，s2或（2）我们＃已存储的内容（意思是 a ＃将在此处排除） ＃因此涵盖了所有三个可能性＃。 D2 [abs（d2）] = max（D2 [abs（d2）]，s2）

最后，我们存储了在d = 0时可见的最高A + B，其中A和B中的元素形成不交集。返回（A + B）/ 2。

I need a clarification of the answer of this question but I can not comment (not enough rep) so I ask a new question. Hope it is ok.

The problem is this:

Given an array, you have to find the max possible two equal sum, you can exclude elements.

i.e 1,2,3,4,6 is given array we can have max two equal sum as 6+2 = 4+3+1

i.e 4,10,18, 22, we can get two equal sum as 18+4 = 22

what would be your approach to solve this problem apart from brute force to find all computation and checking two possible equal sum?

edit 1: max no of array elements are N <= 50 and each element can be up to 1<= K <=1000

edit 2: Total elements sum cannot be greater than 1000.

The approved answer says:

I suggest solving this using DP where instead of tracking A,B (the size of the two sets), you instead track A+B,A-B (the sum and difference of the two sets).

Then for each element in the array, try adding it to A, or B, or neither.

The advantage of tracking the sum/difference is that you only need to keep track of a single value for each difference, namely the largest value of the sum you have seen for this difference.

What I do not undertand is:

If this was the subset sum problem I could solve it with DP, having a memoization matrix of (N x P), where N is the size of the set and P is the target sum...

But I can not figure it out how I should keep track A+B,A-B (as said for the author of the approved answer). Which should be the dimensions of the memoization matrix ? and how that helps to solve the problem ?

The author of the answer was kind enough to provide a code example but it is hard to me to undertand since I do not know python (I know java).

解决方案

I think thinking how this solution relates to the single subset problem might be misleading for you. Here we are concerned with a maximum achievable sum, and what's more, we need to distinguish between two disjoint sets of numbers as we traverse. Clearly tracking specific combinations would be too expensive.

Looking at the difference between sets A and B, we can say:

A - B = d A = d + B

Clearly, we want the highest sum when d = 0. How do we know that sum? It's (A + B) / 2!

For the transition in the dynamic program, we'd like to know if it's better to place the current element in A, B or neither. This is achieved like this:

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

Let's look at Peter de Rivas' code for the transition:

# update a copy of our map, so # we can reference previous values, # while assigning new values D2=D.copy() # d is A - B # s is A + B for d,s in D.items(): # a new sum that includes element a # we haven't decided if a # will be in A or B s2 = s + a # d2 will take on each value here # in turn, once d - a (adding a to B), # and once d + a (adding a to A) for d2 in [d-a, d+a]: # The main transition: # the two new differences, # (d-a) and (d+a) as keys in # our map get the highest sum # seen so far, either (1) the # new sum, s2, or (2) what we # already stored (meaning `a` # will be excluded here) # so all three possibilities # are covered. D2[abs(d2)] = max(D2[abs(d2)], s2)

In the end we have stored the highest A + B seen for d = 0, where the elements in A and B form disjoint sets. Return (A + B) / 2.