简单的01背包 背包容量为所有石子的重量的一半。
#include<stdio.h>
long n,i,sum,now,j;
long f[2000001],v[21];
int main()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
scanf("%ld",&v[i]);
sum+=v[i];
}
now=sum/2;f[0]=1;
for (i=1;i<=n;i++)
for (j=now;j>=v[i];j--)
if (f[j-v[i]]==1)
f[j]=1;
for (i=now;i>=0;i--)
if (f[i]==1)
break;
printf("%ld",sum-i*2);
}
posted on 2011-06-27 16:57
梦转千寻 阅读(107)
评论(0) 编辑 收藏 引用