2.2.2 Subset Sums 集合

2.2.2 Subset Sums 集合

时间： 1ms        内存：64M

描述：

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

{3} and {1,2}
这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）
如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:

{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出

输入：

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

输出：

输出划分方案总数，如果不存在则输出0。

示例输入：

7

示例输出：

4

提示：

参考答案（内存最优[1280]）：

/*
ID: supersnow0622
PROG: test
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include<memory.h>
using namespace std;
int half;
long long c1[500],c2[500],c[500];
int main() {
    ofstream fout ("test.out");
    ifstream fin ("test.in");
    int N,sum;
    cin>>N;
    sum=(1+N)*N/2;
    if(sum%2!=0)
     cout<<0;
    else
    {
      half=sum/2;
      c1[0]=c1[1]=1;

      for(int i=2;i<=N;i++)
        {
         memset(c2,0,sizeof(c2));
         memset(c,0,sizeof(c));
         c2[0]=c2[i]=1;
         for(int j=0;j<=half;j++)
          {
            c[j+0]+=c1[j]*c2[0];
            c[j+i]+=c1[j]*c2[i];
          }
         for(int k=0;k<=half;k++)
          c1[k]=c[k];
        }
      cout<<c1[half]/2;
    }
    return 0;
}

参考答案（时间最优[0]）：

/*
背包问题。如果M=n*(n+1)/2是奇数，则没有分法。如果是偶数，
背包容量为M/2，dp[k] += dp[k-i],(i=1,2,...,n)计算k的时候为避免重算，
需倒着进行。
*/
#include <iostream>

using namespace std;

long long dp[10000];
int n,Max;
int main()
{
    int i,j;
    cin>>n;
    Max=n*(n+1)/2;
    if(Max&1)  //若总和为奇数，则不存在划分方案，输出0
        cout<<0<<endl;
    else
    {
        Max/=2;  //输出结果应除以2，因为互补的结果导致重复
        dp[0]=1;
/*状态转移方程为f(i,j)=f(i-1,j-i)+f(i-1,j)(j>=i),其边界条件为
  f(i,0)=1(i=1,2,...,N),f(i,j)的意义为1,2,...,i可以有多少种方式组成和为j的集合
*/
        for(i=1;i<=n;++i)
            for(j=Max;j>=i;--j)
                dp[j]+=dp[j-i];
        cout<<dp[Max]/2<<endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。