01背包
View Code
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 int wi[10000],f[1000050]; 7 int main(){ 8 int i,fmax,n,sum,j; 9 while(scanf("%d%d",&n,&fmax)==2){ 10 for(i=1,sum=0;i<=n;i++){ 11 scanf("%d",&wi[i]); 12 sum+=wi[i]; 13 } 14 memset(f,0,sizeof(f)); 15 for(i=1;i<=n;i++){ 16 for(j=sum;j>=0;j--){ 17 if(j>=wi[i]){ 18 f[j]=max(f[j],f[j-wi[i]]+wi[i]); 19 } 20 } 21 } 22 //if(f[famx]==famx){printf("0\n");continue;} 23 for(i=fmax;i<=sum;i++){ 24 if(f[i]>=fmax){ 25 printf("%d\n",f[i]-fmax); 26 break; 27 } 28 }} 29 return 0; 30 }