Advertisement
Josif_tepe

Untitled

Nov 1st, 2021
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. long long dp[105][100005];
  6. int main()
  7.  
  8. {
  9.     int n, W;
  10.     cin >> n >> W;
  11.     vector<int> weight(n), value(n);
  12.     for(int i = 0; i < n; i++) {
  13.         cin >> weight[i] >> value[i];
  14.     }
  15.     for(int i = 0; i < 101; i++) {
  16.         for(int j = 0; j < 100001; j++) {
  17.             dp[i][j] = -1e18;
  18.         }
  19.     }
  20.    
  21.     dp[0][W] = 0;
  22.     for(int i = 0; i < n; i++) {
  23.         for(int w = W; w >= 0; w--) {
  24.             if(w - weight[i] >= 0) {
  25.                 dp[i + 1][w - weight[i]] = max(dp[i + 1][w - weight[i]], dp[i][w] + value[i]);
  26.             }
  27.             dp[i + 1][w] = max(dp[i + 1][w], dp[i][w]);
  28.         }
  29.     }
  30.     long long result = -1e18;
  31.     for(int i = 0; i <= W; i++) {
  32.         result = max(result, dp[n][i]);
  33.     }
  34.     cout << result << endl;
  35.     return 0;
  36. }
  37.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement