1 #include<iostream>   2 using namespace std;   3 long f[51][50001];   4 int q1[51];   5 int q2[51];   6 int main()   7 {    8     int k,v,n;   9     int value,weight;  10     cin>>k>>v>>n;  11     for(int i=0;i<=k;i++)  12         for(int j=0;j<=v;j++)  13             f[i][j]=-99999999;//赋初值14     f[1][0]=0;//当背包容量为0时，赋值015     for(int i=1;i<=n;i++)//枚举背包  16     {  17         cin>>weight>>value;  18         for(int j=v;j>=weight;j--)//枚举容量19         {  20             for(int w=1;w<=k;w++)//枚举k包 从1-k21             {  22             q1[w]=f[w][j];  23             q2[w]=f[w][j-weight]+value;  24             }25             int h1=1,h2=1,h=0;  26             while(h<k)27             {  28                 h++;  29                 if(q1[h1]>q2[h2]) {  30                     f[h][j]=q1[h1];  31                     h1++;  32                 }  33                 else {  34                     f[h][j]=q2[h2];  35                     h2++;  36                 }  37             }  38         }  39     }40         int ans=0;  41         for(int i=1;i<=k;i++)  42             ans+=f[i][v];  43         cout<<ans<<endl;  44         return 0;  45 }