蓝桥杯备考：特殊01背包问题——》集合subset
我们划分成两个集合，实际上我们只需要看一部分就行了，也就是从集合的所有元素里挑出恰好满足集合总和的一半儿，当然，如果我们的集合总和是奇数的话，我们是无论如何也挑不出刚好一半儿的，因为我们没有小数，然后这道题就变成了01背包问题，我们要从集合的所有元素里挑出恰好等于sum/2的所有搭配 由于我们选的是有重复的，最后结果要除2
我们按步骤做
step1 确定状态表达 f[i][j]表示从1到i的数里挑选出恰好等于j的搭配方案
step2 推导状态转移方程
step3:初始化，我们只需要初始第一列为1就行了
step4:答案就是f[n][sum/2] /2
#include <iostream>
using namespace std;
const int N = 40,M = 1000;
typedef long long ll;
ll f[N][N];
int main()
{
int n;cin >> n;
int sum = ((1+n)*n)/2;
if(sum&1){
cout << 0 << endl;
return 0;
}
sum/=2;
f[0][0] = 1;
for(int i = 1;i<=n;i++)
{
for(int j = 0;j<=sum;j++)
{
f[i][j] = f[i-1][j];
if(j>=i) f[i][j]+=f[i-1][j-i];
}
}
cout << f[n][sum]/2 << endl;
return 0;
}