liusikai 2013-06-30 09:46:00
点我顶贴
收藏
删除
#include<stdio.h>
int max(int x,int y)
{
int z;
if(x>y) z=x;
else z=y;
return z;
}
int main()
{
int value[100],f[10000]={0};
int n,m,i,j,t,s=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&value[i]);
}
for(i=0;i<n;i++)
{
s=s+value[i];
}
m=s/2;/*......此题的总思想是把其转化为01背包问题：我们要求两队的体重相差最小则要求两个队
的体重都到达最大值（在题目给的数据中），当两队都达到最大值后必然两队的体重就相差最小，
即两个队朝同一目标靠拢则相异最小。所以两个队最大的体重为所有体重之和的一半（s/2），然后再
背包求出一个两队都能够达到的最大值f[m],则两个队相差最小的体重数为s-2*f[m].*/
for(i=0;i<n;i++)
{
for(j=m;j>0;j--)
{
if(j-value[i]>=0)
{
f[j]=max(f[j],f[j-value[i]]+value[i]);
}
}
}
t=s-2*f[m];
printf("%d\n",t);
return 0;
}