1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int M=20010; 7 int n,v,dp[M],c[M],w[M]; 8 void ZeroOnePack(int cost,int weight){ 9     for(int i=v;i>=cost;i--){10         dp[i]=max(dp[i],dp[i-cost]+weight);11     }12 }13 int main(){14     while(~scanf("%d%d",&n,&v)){15         for(int i=1;i<=n;i++){16             scanf("%d%d",&c[i],&w[i]);17         }18         mt(dp,0);19         for(int i=1;i<=n;i++){20             ZeroOnePack(c[i],w[i]);21         }22         printf("%d\n",dp[v]);23     }24     return 0;25 }

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int M=1024; 7 int w[M],dp[M]; 8 int n,v; 9 void ZeroOnePack(int cost,int weight){10     for(int i=v;i>=cost;i--){11         dp[i]=max(dp[i],dp[i-cost]+weight);12     }13 }14 int main(){15     while(~scanf("%d",&n),n){16         for(int i=1;i<=n;i++){17             scanf("%d",&w[i]);18             if(w[i]>w[1]) swap(w[1],w[i]);19         }20         scanf("%d",&v);21         if(v<5){22             printf("%d\n",v);23             continue;24         }25         v-=5;26         mt(dp,0);27         for(int i=2;i<=n;i++){28             ZeroOnePack(w[i],w[i]);29         }30         printf("%d\n",v+5-dp[v]-w[1]);31     }32     return 0;33 }