寻找2个相等的和子序列,最大总和？

Question

我删除了这个问题的所有故事情节.

Q.你有N个号码.你必须找到2个相等的和子序列,最大总和.您不一定需要使用所有数字.

例如1: -

5
1 2 3 4 1

Sub-sequence 1 : 2 3 // sum = 5
Sub-sequence 2 : 4 1 // sum = 5

Possible Sub-sequences with equal sum are 
{1,2} {3}   // sum = 3
{1,3} {4}   // sum = 4
{2,3} {4,1} // sum = 5

Out of which 5 is the maximum sum.

例2: -

6
1 2 4 5 9 1

Sub-sequence 1 : 2 4 5   // sum = 11
Sub-sequence 2 : 1 9 1   // sum = 11
The maximum sum you can get is 11

约束:

5 <= N <= 50

1<= number <=1000

sum of all numbers is <= 1000

Important: Only <iostream> can be used. No STLs.

N numbers are unsorted.

If array is not possible to split, print 0.

Number of function stacks is limited. ie your recursive/memoization solution won't work.

方法1:

我尝试了一种递归方法,如下所示:

#include <iostream>
using namespace std;

bool visited[51][1001][1001];
int arr[51];
int max_height=0;
int max_height_idx=0;
int N;

void recurse( int idx, int sum_left, int sum_right){
    if(sum_left == sum_right){
        if(sum_left > max_height){
            max_height = sum_left;
            max_height_idx = idx;
        }
    }


    if(idx>N-1)return ;

    if(visited[idx][sum_left][sum_right]) return ;

    recurse( idx+1, sum_left+arr[idx], sum_right);
    recurse( idx+1, sum_left         , sum_right+arr[idx]);
    recurse( idx+1, sum_left         , sum_right);

    visited[idx][sum_left][sum_right]=true;

    /*
       We could reduce the function calls, by check the visited condition before calling the function.
       This could reduce stack allocations for function calls. For simplicity I have not checking those conditions before function calls.
       Anyways, this recursive solution would get time out. No matter how you optimize it.
       Btw, there are T testcases. For simplicity, removed that constraint.
    */
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N;
    for(int i=0; i<N; i++)
        cin>>arr[i];

    recurse(0,0,0);

    cout<< max_height <<"\n";
}

NOTE:通过测试用例.但是超时.

方法2:

I also tried, taking advantage of constraints.

Every number has 3 possible choice:
    1. Be in sub-sequence 1
    2. Be in sub-sequence 2
    3. Be in neither of these sub-sequences 

So
    1. Be in sub-sequence 1 -> sum +  1*number
    2. Be in sub-sequence 2 -> sum + -1*number
    3. None             -> sum

Maximum sum is in range -1000 to 1000. 
So dp[51][2002] could be used to save the maximum positive sum achieved so far (ie till idx).

码:

#include <iostream>
using namespace std;

int arr[51];
int N;
int dp[51][2002];

int max3(int a, int b, int c){
    return max(a,max(b,c));
}
int max4(int a, int b, int c, int d){
    return max(max(a,b),max(c,d));
}

int recurse( int idx, int sum){

    if(sum==0){
        // should i perform anything here?
    }

    if(idx>N-1){
        return 0;
    }

    if( dp[idx][sum+1000] ){
        return dp[idx][sum+1000];
    }

    return dp[idx][sum+1000] = max3 (
                                arr[idx] + recurse( idx+1, sum + arr[idx]),
                                    0    + recurse( idx+1, sum - arr[idx]),
                                    0    + recurse( idx+1, sum           )
                               )  ;

    /*
        This gives me a wrong output.

        4
        1 3 5 4
    */
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N;
    for(int i=0; i<N; i++)
        cin>>arr[i];

    cout<< recurse(0,0) <<"\n";

}

上面的代码给了我错误的答案.请帮助我解决/纠正这个记忆.

对于相同的迭代方法也是开放的.

Answer 1

你的第二种方法的想法是正确的，它基本上是背包问题的简化。但是，您的代码似乎缺乏明确的契约：该recurse函数应该做什么。

\n\n

这是我的建议：int recurse(int idx, int sum)将位置上的元素分布idx..n-1到三个多重集A, B，C使得sum+sum(A)-sum(B)=0和 返回最大可能值sum(A)，-inf否则（这里-inf有一些硬编码常量，用作无答案的“标记”；我建议对其有一些限制-inf == -1000）。

\n\n

现在您要使用该合约编写递归回溯，然后添加记忆。瞧\xe2\x80\x94，你已经有了一个动态规划解决方案。

\n\n

在递归回溯中，我们有两种不同的情况：

\n\n

\n
1. 没有更多的元素可供分配，也无需做出选择：idx == n。在这种情况下，我们应该检查我们的条件是否成立（sum + sum(A) - sum(B) == 0，即sum == 0）并返回答案。如果sum == 0，则答案为 0。但是，如果sum != 0，则没有答案，我们应该返回永远不会被选为答案的东西，除非整个问题没有答案。由于我们修改了返回值recurse并且不需要额外的ifs，所以它不能简单地为零或偶数-1；它应该是一个经过修改后仍然是“有史以来最糟糕的答案”的数字。我们可以做的最大修改是将所有数字添加到结果值中，因此我们应该选择小于或等于负最大数字和（即-1000）的值，因为现有答案始终严格为正，而虚构答案将始终为非-积极的。
\n
2. 至少有一个剩余元素应分配给A、B或C。做出选择并从三个选项中选择最佳答案。答案是递归计算的。
\n

\n\n

这是我的实现：

\n\n

const int MAXN = 50;\nconst int MAXSUM = 1000;\n\nbool visited[MAXN + 1][2 * MAXSUM + 1]; // should be filled with false\nint dp[MAXN + 1][2 * MAXSUM + 1]; // initial values do not matter\n\nint recurse(int idx, int sum){\n    // Memoization.\n    if (visited[idx][sum + MAXSUM]) {\n        return dp[idx][sum + MAXSUM];\n    }\n    // Mark the current state as visited in the beginning,\n    // it\'s ok to do before actually computing it as we\'re\n    // not expect to visit it while computing.\n    visited[idx][sum + MAXSUM] = true;\n\n    int &answer = dp[idx][sum + MAXSUM];\n\n    // Backtracking search follows.\n    answer = -MAXSUM;  // "Answer does not exist" marker.\n\n    if (idx == N) {\n        // No more choices to make.\n        if (sum == 0) {\n            answer = 0;  // Answer exists.\n        } else {\n            // Do nothing, there is no answer.\n        }\n    } else {\n        // Option 1. Current elemnt goes to A.\n        answer = max(answer, arr[idx] + recurse(idx + 1, sum + arr[idx]));\n        // Option 2. Current element goes to B.\n        answer = max(answer, recurse(idx + 1, sum - arr[idx]));\n        // Option 3. Current element goes to C.\n        answer = max(answer, recurse(idx + 1, sum));\n    }\n    return answer;\n}\n

\n