分区求和算法
Partition Sum algorithm
我被要求输入一个整数列表,并将它们分成两个总和相等的部分。例如,1 3 5 7 的列表将被划分为 1+7 和 3+5。这是我到目前为止的代码。我只是在寻找比蛮力更快的方法。
#include <iostream>
using namespace std;
int main()
{
int input,n,temp,sum = 0;
int Asum, Bsum;
cout << "Number of inputs: ";
cin >> n;
cout << "Enter " << n << " numbers: ";
int arr[n];
int partA[n/2];
int partB[n/2];
for(int i = 0; i < n; i++)
{
cin >> temp;
arr[i] = temp;
}
for(int i = 0; i < n; i ++)
sum += arr[i];
cout << sum;
if(sum %2 !=0)
{
cout << "No partition";
}
else
{
sum/=2;
}
return 0;
}
所以我开始了,我们可以将 dp 状态保持为 dp[idx][sum1]
其中 idx 指的是数组中的当前索引,sum1 是分区 1 的总和,使用这两个参数我们可以提取第三个参数是 sum2(sum2 = totalSum - sum1),这将帮助我们减少状态数,剩下的是一个简单的递归 dp 解决方案
#include<bits/stdc++.h>
using namespace std;
int n, arr[100], tot, dp[100][100000], mark[100];
int solve(int idx, int sum1){
if(idx == n){
int sum2 = tot - sum1;
//cout << sum1 << " " << sum2 << endl;
if(sum1 == sum2) return 1;return 0;
}
if(dp[idx][sum1] != -1) return dp[idx][sum1];
int v1 = 0, v2 = 0;
v1 = solve(idx+1, sum1);
v2 = solve(idx+1, sum1 + arr[idx]);
if(v1 + v2 > 0) dp[idx][sum1] = 1;
else dp[idx][sum1] = 0;
return dp[idx][sum1];
}
void check(int idx, int sum1){
if(idx == n) return;
int v1 = solve(idx+1, sum1);
int v2 = solve(idx+1, sum1 + arr[idx]);
if(v1 == 1){
mark[idx] = 1;
check(idx+1, sum1);
}else{
mark[idx] = 2;
check(idx+1, sum1 + arr[idx]);
}
}
int main(){
cin >> n;
for(int i = 0;i < n;i++) cin >> arr[i], tot += arr[i];
memset(dp, -1, sizeof dp);
int ct = solve(0, 0);
if(ct == 0){
cout << "No Partition" << endl;
}else{
check(0, 0);
for(int i = 0;i < n;i++) if(mark[i] == 1) cout << arr[i] << " ";cout << endl;
for(int i = 0;i < n;i++) if(mark[i] == 2) cout << arr[i] << " ";cout << endl;
}
}
Link 致 Ideone : https://ideone.com/6MKLK0
还要记住在定义的dp数组中,index的个数是100,也就是说我们可以求解100个元素,所有元素的总和不能超过100000(也就是第二个参数) ,如果你想增加你需要改变状态的元素的数量,所有元素的总和也是如此。
我被要求输入一个整数列表,并将它们分成两个总和相等的部分。例如,1 3 5 7 的列表将被划分为 1+7 和 3+5。这是我到目前为止的代码。我只是在寻找比蛮力更快的方法。
#include <iostream>
using namespace std;
int main()
{
int input,n,temp,sum = 0;
int Asum, Bsum;
cout << "Number of inputs: ";
cin >> n;
cout << "Enter " << n << " numbers: ";
int arr[n];
int partA[n/2];
int partB[n/2];
for(int i = 0; i < n; i++)
{
cin >> temp;
arr[i] = temp;
}
for(int i = 0; i < n; i ++)
sum += arr[i];
cout << sum;
if(sum %2 !=0)
{
cout << "No partition";
}
else
{
sum/=2;
}
return 0;
}
所以我开始了,我们可以将 dp 状态保持为 dp[idx][sum1]
其中 idx 指的是数组中的当前索引,sum1 是分区 1 的总和,使用这两个参数我们可以提取第三个参数是 sum2(sum2 = totalSum - sum1),这将帮助我们减少状态数,剩下的是一个简单的递归 dp 解决方案
#include<bits/stdc++.h>
using namespace std;
int n, arr[100], tot, dp[100][100000], mark[100];
int solve(int idx, int sum1){
if(idx == n){
int sum2 = tot - sum1;
//cout << sum1 << " " << sum2 << endl;
if(sum1 == sum2) return 1;return 0;
}
if(dp[idx][sum1] != -1) return dp[idx][sum1];
int v1 = 0, v2 = 0;
v1 = solve(idx+1, sum1);
v2 = solve(idx+1, sum1 + arr[idx]);
if(v1 + v2 > 0) dp[idx][sum1] = 1;
else dp[idx][sum1] = 0;
return dp[idx][sum1];
}
void check(int idx, int sum1){
if(idx == n) return;
int v1 = solve(idx+1, sum1);
int v2 = solve(idx+1, sum1 + arr[idx]);
if(v1 == 1){
mark[idx] = 1;
check(idx+1, sum1);
}else{
mark[idx] = 2;
check(idx+1, sum1 + arr[idx]);
}
}
int main(){
cin >> n;
for(int i = 0;i < n;i++) cin >> arr[i], tot += arr[i];
memset(dp, -1, sizeof dp);
int ct = solve(0, 0);
if(ct == 0){
cout << "No Partition" << endl;
}else{
check(0, 0);
for(int i = 0;i < n;i++) if(mark[i] == 1) cout << arr[i] << " ";cout << endl;
for(int i = 0;i < n;i++) if(mark[i] == 2) cout << arr[i] << " ";cout << endl;
}
}
Link 致 Ideone : https://ideone.com/6MKLK0
还要记住在定义的dp数组中,index的个数是100,也就是说我们可以求解100个元素,所有元素的总和不能超过100000(也就是第二个参数) ,如果你想增加你需要改变状态的元素的数量,所有元素的总和也是如此。