0-1背包问题O(N*(N+1)/2)
难点在于转化题意,转化好了就是一个简单的0-1背包问题
题目希望我们将1~N之间的数划分成两个相等的集合
可以转化成,对于数N*(N+1)/2,从1~N中挑选出整数相加==N*(N+1)/2
每个数可以选或者不选,最终体积为N*(N+1)/2
#include<iostream>
using namespace std;
const int N=400;
long long f[N];
int main()
{
int n;
cin>>n;
int m=n*(n+1)/2;
if(m%2) cout<<"0"<<endl;
else{
m/=2;
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=i;j--)
f[j]+=f[j-i];
}
cout<<f[m]/2<<endl;
}
}