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

Question

我需要澄清这个问题的答案，但我不能评论(没有足够的代表)，所以我问一个新的问题。希望没问题。

问题是这样的：

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

即1，2，3，4，6是给定的数组，我们可以得到最大两个相等的和，如6 2 = 4 3 1

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

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

编辑1：数组元素的最大数量为N

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

被认可的回答说:

我建议使用DP来解决这个问题，这里不跟踪A，B（两个集合的大小），而是跟踪A，B，A-B（两组的和和和和差）。

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

跟踪和/差的好处是，你只需要跟踪每个差的单个值，即你看到的这个差的和的最大值。

我不明白的是:

如果这是一个子集和问题，我可以用DP来解决它，有一个记忆矩阵（N x P），其中N是集合的大小，P是目标和。。。

但是我无法弄清楚我应该如何跟踪A B，A-B（正如批准答案的作者所说）。哪些应该是记忆矩阵的维度？以及这如何帮助解决问题？

答案的作者非常友好地提供了一个代码示例，但我很难理解，因为我不懂python（我懂java）。

Answer 1

#include <bits/stdc++.h>
using namespace std;

/*
    Brute force recursive solve.
*/

void solve(vector<int>&arr, int &ans, int p1, int p2, int idx, int mx_p){
    
    // if p1 == p2, we have a potential answer
    if(p1 == p2){
        ans = max(ans, p1);
    }
    
    //base case 1:
    if((p1>mx_p) || (p2>mx_p) || (idx >= arr.size())){
        return;
    }
    
    // leave the current element
    solve(arr, ans, p1, p2, idx+1, mx_p);

    // add the current element to p1
    solve(arr, ans, p1+arr[idx], p2, idx+1, mx_p);

    // add the current element to p2
    solve(arr, ans, p1, p2+arr[idx], idx+1, mx_p);
}

/*
    Recursive solve with memoization.
*/

int solve(vector<vector<vector<int>>>&memo, vector<int>&arr,
                                int p1, int p2, int idx, int mx_p){

    //base case 1:
    if((p1>mx_p) || (p2>mx_p) || (idx>arr.size())){
        return -1;
    }
    
    // memo'ed answer
    if(memo[p1][p2][idx]>-1){
        return memo[p1][p2][idx];
    }


    // if p1 == p2, we have a potential answer
    if(p1 == p2){
        memo[p1][p2][idx] = max(memo[p1][p2][idx], p1);
    }
    
    // leave the current element
    memo[p1][p2][idx] = max(memo[p1][p2][idx], solve(memo, arr, p1, p2, 
                           idx+1, mx_p));

    // add the current element to p1
    memo[p1][p2][idx] = max(memo[p1][p2][idx], 
                            solve(memo, arr, p1+arr[idx], p2, idx+1, mx_p));

    // add the current element to p2
    memo[p1][p2][idx] = max(memo[p1][p2][idx], 
                            solve(memo, arr, p1, p2+arr[idx], idx+1, mx_p));
                            
    return memo[p1][p2][idx];
}

int main(){
    
    vector<int>arr = {1, 2, 3, 4, 7};
    int ans = 0;
    int mx_p = 0;
    
    for(auto i:arr){
        mx_p += i;
    }
    mx_p /= 2;
    
    vector<vector<vector<int>>>memo(mx_p+1, vector<vector<int>>(mx_p+1, 
                                    vector<int>(arr.size()+1,-1)));
    ans = solve(memo, arr, 0, 0, 0, mx_p);
    ans = (ans>=0)?ans:0;
    
    // solve(arr, ans, 0, 0, 0, mx_p);
    cout << ans << endl;
    return 0;
}

Answer 2

试试这个dp方法：它工作正常。

/*
 * 
 i/p ::

1
5
1 2 3 4 6
o/p : 8

1
4
4 10 18 22
o/p : 22


1
4
4 118 22 3
o/p : 0
 */
import java.util.Scanner;

public class TwoPipesOfMaxEqualLength {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] arr = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                arr[i] = sc.nextInt();
            }
            MaxLength(arr, n);
        }
    }

    private static void MaxLength(int[] arr, int n) {

        int dp[][] = new int[1005][1005];
        int dp1[][] = new int[1005][1005];

        // initialize dp with values as 0.
        for (int i = 0; i <= 1000; i++) {
            for (int j = 0; j <= 1000; j++)
                dp[i][j] = 0;
        }

        // make (0,0) as 1.
        dp[0][0] = 1;


        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 1000; j++) {
                for (int k = 0; k <= 1000; k++) {
                    if (j >= arr[i]) {
                        if (dp[j - arr[i]][k] == 1) {
                            dp1[j][k] = 1;## Heading ##
                        }
                    }
                    if (k >= arr[i]) {
                        if (dp[j][k - arr[i]] == 1) {
                            dp1[j][k] = 1;
                        }
                    }
                    if (dp[j][k] == 1) {
                        dp1[j][k] = 1;
                    }
                }
            }

            for (int j = 0; j <= 1000; j++) {
                for (int k = 0; k <= 1000; k++) {
                    dp[j][k] = dp1[j][k];
                    dp1[j][k] = 0;
                }
            }
        }

        int ans = 0;

        for (int i = 1; i <= 1000; i++) {
            if (dp[i][i] == 1) {
                ans = i;
            }
        }

        System.out.println(ans);

    }

}

Answer 3

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

看看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的过渡代码：

# 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)

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