題目大意：給出n個數(shù)，分成兩組，每組和的差盡量小。
背包問題。計算出n個數(shù)所有的組合情況即可。具體做法是，如果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 閱讀(705)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃