题目大意：给出n个数，分成两组，每组和的差尽量小。
背包问题。计算出n个数所有的组合情况即可。具体做法是，如果d[j]==true，那么d[j+r[i]]也一定为true。
以下是我的代码：
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(107);
int n,sum,r[kMaxn];
bool d[50007];
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
int T;
scanf("%d",&T);
while(T--)
{
sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&r[i]);
sum+=r[i];
}
memset(d,false,50007*sizeof(bool));
d[0]=true;
for(int i=1;i<=n;i++)
for(int j=sum-d[i];j>=0;j--)
if(d[j])
d[j+r[i]]=true;
for(int i=(sum>>1);i>=0;i--)
if(d[i])
{
printf("%d\n",sum-(i<<1));
break;
}
}
return 0;
}
posted on 2011-05-25 20:13
lee1r 阅读(662)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划