给定 \(N\) 个数 \(A_1,\cdots ,A_N\)，问可不可以把它们分成两组，使得两组的和相同。
没有数据范围。
有一个很简单的 dp 方法，\(dp_{i,x}|=dp_{i-1,x-a_i}\)。 看 \(dp_{n,\frac{sum}{2}}\) 是否为 \(1\)。时间复杂度 \(O(N\times \sum_{i=1}^{N}A_i)\)。
code
#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<#x<<"="<<x<<endl
using ll = long long;
const int N = 5e2+2;
const int M = 5e5+5;
int n,sum;
int a[N];
bool dp[N][M];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
freopen("input.txt","r",stdin);
freopen("ans.txt","w",stdout);
cin>>n;
for (int i=1; i<=n; i++){
cin>>a[i];
sum+=a[i];
}
dp[0][0]=1;
for (int i=1; i<=n; i++){
for (int j=0; j<M; j++){
dp[i][j]|=dp[i-1][j];
if (j>=a[i]){
dp[i][j]|=dp[i-1][j-a[i]];
}
}
}
if (sum%2==0 && dp[n][sum/2]){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}
// don't waste time!!!
但是，这个方法和 \(A\) 的值域有关，\(\max A_i\) 或 \(\sum_{i=1}^{n} A_i\) 大的时候不会很好。
我尝试了一个随机的方法，是这样的。
每一次 \(random\ shuffle\) 一次，贪心选择。如果 \(cur\ge A_i\)（\(cur\) 从 \(\frac{sum}{2}\) 开始）就选，否则不选。成功概率是什么呢？
code
#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<#x<<"="<<x<<endl
using ll = long long;
const int N = 1e3+3;
int n;
int a[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int sum=0;
cin>>n;
for (int i=1; i<=n; i++){
cin>>a[i];
sum+=a[i];
}
if (sum&1){
cout<<"NO"<<endl;
return 0;
}
sum/=2;
for (int ti=1; ti<=50; ti++){
random_shuffle(a+1,a+1+n);
for (int i=1; i<=n; i++){
if (sum>=a[i]){
sum-=a[i];
}
}
if (sum==0){
cout<<"YES"<<endl;
return 0;
}
}
cout<<"NO"<<endl;
return 0;
}
// don't waste time!!!
我写了一个随机数据生成器。
generator
#include <bits/stdc++.h>
using namespace std;
#define de(x) cout<<#x<<"="<<x<<endl
using ll = long long;
const int N = 500;
const int A = 1000;
mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y){
return uniform_int_distribution<int>(x, y)(rng);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
freopen("input.txt","w",stdout);
cout<<N<<endl;
for (int i=1; i<=N; i++){
cout<<rnd(1,A)<<" ";
}
cout<<endl;
return 0;
}
// don't waste time!!!
跑了 \(1000\) 组数据，成功率 \(84.1\%\)。
如果 \(N,A\) 分别改成 \(1000,100\)，成功率 \(100\%\)。
有没有更好的方法？待更。
标签：cout,一个,sum,namespace,问题,int,有趣,include,dp From： https://www.cnblogs.com/SFlyer/p/17601416.html