Advertisement
Josif_tepe

Untitled

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