Advertisement
Josif_tepe

Untitled

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