01背包

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int n,c;
 6     cin>>n>>c;
 7     int w[n+1],v[n+1];
 8     for(int i=1;i<=n;i++)
 9     {
10         cin>>w[i]>>v[i];
11     }
12     long long dp[n+1][c+1];
13     memset(dp,0,sizeof(dp));
14     for(int i=1;i<=n;i++)
15     {
16         for(int j=0;j<=c;j++)
17         {
18             if(w[i]>j)
19             {
20                 dp[i][j]=dp[i-1][j];
21             }
22             else
23             {
24                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
25             }
26         }
27     }
28     cout<<dp[n][c]<<endl;
29     return 0;
30 }