对于从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。程序不能预存结果直接输出。
PROGRAM NAME: subset
INPUT FORMAT
输入文件只有一行，且只有一个整数N
SAMPLE INPUT (file subset.in)
7
OUTPUT FORMAT
输出划分方案总数，如果不存在则输出0。
SAMPLE OUTPUT (file subset.out)
4
/************************************************************************/
/* 1到n的自然数之和为：1+2+3……+n=n*(n+1)/2
题目要求：对于从1到N的连续整集合，划分为两个子集合，且保证每个集合的数字和
是相等的。因而，划分之后每个子集全的数字应该为n*(n+1)/2的一半，即n*(n+1)/4
由于两个子集中都是整数，所以n*(n+1)必为偶数，则可以设s=n*(n+1),并判断s%4 .
则，s/=4是划分之后子集合的数字和；dyn[i]数组表示任意个数加起来等于i的组数*/
/************************************************************************/
动态规划
#include<iostream>
#include<malloc.h>
using namespace std;
int main()
{
int dyn[100];
memset(dyn,0,100);
int n,s;
cin>>n;
s=n*(n+1);
if(s%4)
{
cout<<0<<endl;
}
s/=4;
int i,j;
dyn[0]=1;
for(i=1;i<=n;i++)//表示这个次选取的是数为i
{
for(j=s;j>=i;j--)
dyn[j]+=dyn[j-i];//dyn[j-i]表示加起来等于j-i的组数，
} //dyn[j]表示加起来等于j的组数
cout<<dyn[s]/2<<endl;//由于交换两个子集合的位置被认为是同一种划分方案，所以最终结果为dyn[s]/2
return 1;
}
/************************************************************************/
/* 背包方法
可以将问题转变为01背包恰好装满的情况；将原集合分为两部分，每部分中数的和均
为n(n+1)/4,则问题转变为从原集合中取物品，放入背包容量为n(n+1)/4的背包中，且
恰好装满，有多少种取法。最后将所求得的方法数除以2即为可划分的子集合数*/
/************************************************************************/
#include<iostream>
#include<malloc.h>
using namespace std;
int main()
{
int Pos[10];
int top=0;
int Array[]={1,2,3,4,5,6,7};
int m=14;//背包容量m=n(n+1)/4;
int n=7;//物品个数
int i,j;
int count=0;//满足条件的方法数
i=0;
memset(Pos,0,sizeof(Pos));
while(i<=n&&top>=0)
{
while(m>0&&i<n)
{
if(Array[i]<=m)
{
Pos[top++]=i;
m-=Array[i];
}
i++;
}
if(m==0)
{
for(j=0;j<top;j++)
{
cout<<" "<<Array[Pos[j]];
}
cout<<endl;
count++;
}
i=Pos[--top];
if(top<0)break;
Pos[top]=0;
m+=Array[i];
i++;
}
cout<<"可分为组数："<<count/2;
}
转播
