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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注