51Nod 1085 背包问题

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 1000000 + 5;
 7 int v[maxn];
 8 int c[maxn];
 9 int dp[maxn];
10 
11 int main(){
12     ios::sync_with_stdio(false);
13     int n, w;
14     cin >> n >> w;
15     for (int i = 1; i <= n; i++){
16         cin >> v[i] >> c[i];
17     }
18     memset(dp, 0, sizeof(dp));
19     for (int i = 1; i <= n; i++){
20         for (int j = w; j >= 0; j--){
21             if (v[i]<=j)
22             dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
23         }
24     }
25     cout << dp[w] << endl;
26     return 0;
27 }