Advertisement
Josif_tepe

Untitled

Nov 3rd, 2021
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 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.     int sum = 0;
  15.     for(int i = 0; i < n; i++) {
  16.         cin >> weight[i] >> value[i];
  17.         sum += value[i];
  18.     }
  19.     for(int i = 0; i <= n; i++) {
  20.         for(int j = 0; j <= sum; j++) {
  21.             dp[i][j] = 1e18;
  22.         }
  23.     }
  24.     dp[0][0] = 0;
  25.     for(int i = 0; i < n; i++) {
  26.         for(int j = 0; j <= sum; j++) {
  27.             dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
  28.             if(j + value[i] <= sum) {
  29.                 dp[i + 1][j + value[i]] = min(dp[i + 1][j + value[i]], dp[i][j] + weight[i]);
  30.             }
  31.         }
  32.     }
  33.     for(int i = sum; i >= 0; i--) {
  34.         if(dp[n][i] <= W) {
  35.             cout << i << endl;
  36.             break;
  37.         }
  38.     }
  39.     return 0;
  40. }
  41.  
  42.  
  43.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement