USACO C2S2.2 Subset Sums 解题报告

算法标签：动态规划

题目链接：OpenJudge - 072:C2S2.2 集合

题目描述

　　对于从 1～n 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果 n=3，对于 {1,2,3} 能划分成两个子集合，每个子集合的所有数字和是相等的：

　　{3} 和 {1,2} 是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）

　　如果 n=7，有四种方法能划分集合 {1,2,3,4,5,6,7}，每一种分法的子集合各数字和是相等的:

　　{1,6,7} 和 {2,3,4,5}

　　{2,5,7} 和 {1,3,4,6}

　　{3,4,7} 和 {1,2,5,6}

　　{1,2,4,7} 和 {3,5,6}

　　给出 n，你的程序应该输出划分方案总数。

输入格式

输入文件只有一行，且只有一个整数 n 。

输出格式

输出划分方案总数。

样例输入

7

样例输出

4

数据范围

对于 100% 的数据，1<=n<=39。

解法一：

　　本题可以转化成背包问题，题目让我们把集合中的元素分成和相等的两个部分，也就是说元素总和除以2就是背包容量，状态f[i][j]可设置为前i个元素装满容量为j的背包的方案数，其状态转移方程为：

当j>=i时，方案数为不取和取的方案数之和 f[i][j]=f[i-1][j]+f[i-1][j-i]

当j

另外：

1、我们可以先判断n个元素总和的奇偶性，能够平分的前提是总和为偶数；

2、当n=3时，{3}和{1,2}都可以装满容量为3的背包，但它们是同一种划分方案，所以最后背包中的方案数要除以2；

3、当n=39时，背包方案总数会超出int范围（除以2之后又会回到int 范围）。

#include
using namespace std;
int sum,n;
long long f[45][405];
int main() {
  cin>>n;
  sum=(n*(n+1))/2;
  if (sum%2==1) {
    cout<<0;
    return 0;
  }
  sum/=2;
  f[1][0]=1;  //从1中取任意个数的数使和为0的情况数
  f[1][1]=1;  //从1中取任意个数的数使和为1的情况数

  for (int i=2;i<=n;i++)
    for (int j=0;j<=sum;j++)
      if (j>=i) f[i][j]=f[i-1][j]+f[i-1][j-i];
      else f[i][j]=f[i-1][j];

  cout<

解法二：还可以进一步压缩成一维数组，不过循环顺序就必须是倒序了。

#include
using namespace std;
int n,sum;
long long f[405];
int main() {
  cin>>n;
  sum = n*(n+1)/2;
  if(sum%2==1) {
    cout<<0;
    return 0;
  }
  sum >>= 1;
  f[0] = 1;
  for(int i = 1; i <= n; i++)
    for(int j = sum; j >= i; j--)
      f[j] += f[j-i];
  cout<