找到2个相等的总和子序列，且总和最大？ [英] Finding 2 equal sum sub-sequences, with maximum sum?
问题描述
我已删除此问题的所有故事情节。
I have removed all the storylines for this question.
Q。您得到N个数字。您必须找到2个相等和的子序列，且最大和。您不一定需要使用所有数字。
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.
例如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：
我尝试了类似以下的递归方法：
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.
方法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";
}
上面的代码给了我错误的答案。请帮助我解决/纠正这种记忆。
The above code gives me wrong answer. Kindly help me with solving/correcting this memoization.
也可以采用相同的迭代方法。
Also open to iterative approach for the same.
推荐答案
第二种方法的想法是正确的，基本上可以简化为背包问题。但是，您的代码似乎缺少清晰的合同：递归函数应该执行的操作。
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.
这是我的建议： int recurse（int idx，int sum）将元素分配到位置 idx..n-1 分为三个多重集 A ， B ， C 使得 sum + sum（A）-sum（B）= 0 并返回最大可能的 sum（A）， -inf 否则（此处 -inf 是一些硬编码的常量，可作为无答案的标记；对此有一些限制，我建议 -inf == -1000 ）。
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:
- 没有更多元素可以分配，没有其他选择：
idx == n。在这种情况下，我们应该检查条件是否成立（sum + sum（A）-sum（B）== 0，即sum == 0）并返回答案。如果sum == 0，则答案为0。但是，如果sum！= 0，则没有答案。答案，我们应该返回永远不会被选择为答案的内容，除非整个问题没有答案。由于我们修改了recurse的返回值，并且不希望额外的if，因此它不能简单地为零甚至-1;它应该是一个经过修改的数字，仍然是有史以来最糟糕的答案。我们可以做的最大修改是将所有数字加到结果值上，因此我们应该选择小于或等于负的最大数字和（即-1000），例如现有答案始终严格是肯定答案，而虚构答案始终是非肯定答案。 - 至少有一个剩余元素应分配给
A，B或C。做出选择，然后从三个选项中选择最佳答案。答案是递归计算的。
- 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. Ifsum == 0, then the answer is 0. However, ifsum != 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 ofrecurseand do not want extraifs, 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. - There is at least one remaining element which should be distributed to either
A,BorC. Make the choice and choose the best answer among three options. Answers are calculated recursively.
这是我的实现：
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个相等的总和子序列，且总和最大？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
