Finding 2 equal sum sub-sequences, with maximum su

问题:

I have removed all the storylines for this question.

Q. You are given N numbers. You have to find 2 equal sum sub-sequences, with maximum sum. You don't necessarily need to use all numbers.

Eg 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.

Eg 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

Constraints:

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.

Approach 1:

I tried a recursive approach something like the below:

#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: Passes test-cases. But time out.

Approach 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).

CODE:

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

}

The above code gives me wrong answer. Kindly help me with solving/correcting this memoization.

Also open to iterative approach for the same.

回答1:

Idea of your second approach is correct, it's basically a reduction to the knapsack problem. However, it looks like your code lacks clear contract: what the recurse function is supposed to do.

Here is my suggestion: int recurse(int idx, int sum) distributes elements on positions idx..n-1 into three multisets A, B, C such that sum+sum(A)-sum(B)=0 and returns maximal possible sum(A), -inf otherwise (here -inf is some hardcoded constant which serves as a "marker" of no answer; there are some restrictions on it, I suggest -inf == -1000).

Now you're to write a recursive backtracking using that contract and then add memoization. Voila—you've got a dynamic programming solution.

In recursive backtracking we have two distinct situations:

1. There are no more elements to distribute, no choices to make: idx == n. In that case, we should check that our condition holds (sum + sum(A) - sum(B) == 0, i.e. sum == 0) and return the answer. If sum == 0, then the answer is 0. However, if sum != 0, then there is no answer and we should return something which will never be chosen as the answer, unless there are no answer for the whole problem. As we modify returning value of recurse and do not want extra ifs, it cannot be simply zero or even -1; it should be a number which, when modified, still remains "the worst answer ever". The biggest modification we can make is to add all numbers to the resulting value, hence we should choose something less or equal to negative maximal sum of numbers (i.e. -1000), as existing answers are always strictly positive, and that fictive answer will always be non-positive.
2. There is at least one remaining element which should be distributed to either A, B or C. Make the choice and choose the best answer among three options. Answers are calculated recursively.

Here is my implementation:

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:

State is not updated in Approach 1. Change the last line of recurse

visited[idx][sum_left][sum_right];

to

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

Also memset the visited array to false before calling recurse from main.