找到2个相等的总和子序列，且总和最大？

  • Z时代
  • 2024-01-10
  • 分类：问答

我已删除该问题的所有故事情节。

Q.给您N个数字。您必须找到2个相等和的子序列，且最大和。您不一定需要使用所有数字。

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.

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.

我尝试了类似以下的递归方法：

#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:通过测试用例。但是超时。

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";
}

上面的代码给了我错误的答案。请帮助我解决/更正此备注。

同样也可以采用迭代方法。

回答：

第二种方法的想法是正确的，基本上可以简化背包问题。但是，您的代码似乎缺乏

：该recurse函数应该做什么。

这里是我的建议：int recurse(int idx, int

sum)在岗位分配要素idx..n-1分为三个多集A，B，C使得sum+sum(A)-sum(B)=0返回最大可能sum(A)，-inf否则（这里-inf是一些硬编码的常量，它作为一个没有答案的“标记”;也有它的一些限制，我建议-inf

== -1000）。

现在，您将使用该合同编写一个递归回溯，然后添加备忘录。瞧-您有一个动态的编程解决方案。

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

  1. 没有更多要分配的元素，也没有做出选择的选择idx == n。在这种情况下，我们应该检查条件是否成立（sum + sum(A) - sum(B) == 0，即sum == 0）并返回答案。如果为sum == 0，则答案为0。但是，如果为sum != 0，则没有答案，我们应该返回永远不会被选择为答案的内容，除非对整个问题没有答案。当我们修改的返回值recurse并且不希望有额外的ifs时，它不能简单地为零甚至是-1; 它应该是一个经过修改的数字，仍然是“有史以来最糟糕的答案”。我们可以做的最大修改是将所有数字加到结果值上，因此我们应该选择小于或等于负的最大数字和（即-1000），因为现有答案始终严格地是肯定的，而虚构的答案将始终是非肯定的。

  2. 有应分发到至少一个剩余元件A，B或C。做出选择，然后从三个选项中选择最佳答案。答案是递归计算的。

这是我的实现：

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

以上是 找到2个相等的总和子序列，且总和最大？ 的全部内容， 来源链接： utcz.com/qa/400916.html

回到顶部