Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
程序设计对抗赛设有N（0＜N≤50的整数）个价值互不相同的奖品，每个奖品的价值分别为S1，S2，S3..Sn（均为不超过100的正整数br>）。现将它们分给甲乙两队，为了使得甲乙两队得到相同价值的奖品，必须将这N个奖品分成总价值相等的两组。
编程要求：对给定N及N个奖品的价值，求出将这N个奖品的价值，求出将这N个奖品分成价值相等的两组，共有多少种分法？
例如：N=5,s1,s2,s3……Sn分别为1,3,5,8,9
则可分为{1,3,9}与{5,8}
仅有1种分法；
例如：N=7,S1,S2,S3…..Sn分别为1,2,3,4,5,6,7
有4种分法：
{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及s1,s2,s3….sn。（每两个相邻的数据之间有一个空格隔开）。
【输出格式】
输出文件包含一个整数，表示多少种分法的答案，数据若误解，则输出0
Sample Input
7
1 2 3 4 5 6 7
Sample Output
4
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=9923
【【9923】对抗赛】【题解】
算出所有物品的价值总和;
如果为奇数;
则肯定无解;
(要分成两个价值相同的组)
然后把价值除2
设为m;
然后就相当于一个容量为m的背包;
n个物品;
每个物品的价值也即它的重量;
求背包方案数;
最后的结果除2就好;
因为
eg:
4个物品
1 4 2 3
m=5
则会把1 4 和 2 3两种情况都算进去;
而我们只要确定了一组,剩下的一组其实也就确定了;
这里出现了重复;
因此除2.
【完整代码】
#include
#define rei(x) scanf("%d",&x)
#define rep1(i,x,y) for (int i = x;
i <= y;
i++)
const int MAXN = 50+10;
int n,m;
int s[MAXN];
int f[2500+100];
int main()
{
//freopen("F:\\rush.txt","r",stdin);
rei(n);
rep1(i,1,n)
{
rei(s[i]);
m+=s[i];
}
if (m&1)
{
puts("0");
return 0;
}
m>>=1;
f[0] = 1;
rep1(i,1,n)
for (int j = m;
j >= s[i];
j--)
f[j] += f[j-s[i]];
printf("%d\n",f[m]/2);
return 0;
}
转载于:https://www.cnblogs.com/AWCXV/p/7626694.html
