1 //Accepted    240 KB    188 ms 2 //0-1背包 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 using namespace std; 7 const int imax_n = 3405; 8 const int imax_m = 12885; 9 int f[imax_m];10 int weight[imax_n];11 int factor[imax_n];12 int n;13 int m;14 void Dp()15 {16     memset(f,0,sizeof(f));17     for (int i=0;i<n;i++)18     {19         for (int j=m;j>=weight[i];j--)20         if (f[j]<f[j-weight[i]]+factor[i])21         f[j]=f[j-weight[i]]+factor[i];22     }23     int ans=0;24     for (int i=0;i<=m;i++)25     if (ans<f[i]) ans=f[i];26     printf("%d\n",ans);27 }28 int main()29 {30     while (scanf("%d%d",&n,&m)!=EOF)31     {32         for (int i=0;i<n;i++)33         {34             scanf("%d%d",&weight[i],&factor[i]);35         }36         Dp();37     }38     return 0;39 }