http://acm.nyist.net/JudgeOnline/problem.php?pid=325
5 5 8 13 27 14
3
类似于:http://www.cnblogs.com/zeze/p/ntoj456.html
1 #include<stdio.h> 2 #include<string.h> 3 int max(int x,int y) 4 { 5 if(x>y)return x; 6 else return y; 7 } 8 int main() 9 { 10 int n,i,j,f[100001],c[101]; 11 int t; 12 13 while(scanf("%d",&t)!=EOF) 14 { 15 int sum=0; 16 for(i=1;i<=t;i++) 17 { 18 scanf("%d",&c[i]); 19 sum+=c[i]; 20 } 21 memset(f,0,sizeof(f)); 22 for(i=1;i<=t;i++) 23 { 24 for(j=sum/2;j>=c[i];j--) 25 { 26 //f[j]=max(f[j],f[j-c[i]]+c[i]);//会超时! 27 f[j]=(f[j]>f[j-c[i]]+c[i]?f[j]:f[j-c[i]]+c[i]); 28 } 29 } 30 printf("%d\n",sum-f[sum/2]-f[sum/2]); 31 } 32 return 0; 33 }
原文:http://www.cnblogs.com/zeze/p/nyoj325.html