Advertisement
Josif_tepe

Untitled

Nov 1st, 2021
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <vector>
  6. using namespace  std;
  7. int n, w;
  8. typedef long long ll;
  9. ll memo[105][100005];
  10. ll weight[105];
  11. ll value [105];
  12. ll ks(int i,int value_left){
  13.     if(value_left == 0 ){
  14.         return  0;
  15.     }
  16.     if(i == n ){
  17.         return  2e18;
  18.     }
  19.     if(memo[i][value_left] != -1){
  20.         return  memo[i][value_left];
  21.     }
  22.     ll  result = 2e18;
  23.  
  24.         result = min(result,ks(i+1,value_left));
  25.         if(value_left - value[i] >= 0){
  26.             result = min(result, ks(i+1,value_left -value[i]) + weight[i]);
  27.         }
  28.  
  29.     return  memo[i][value_left]= result;
  30. }
  31. int main() {
  32.  
  33.     cin >> n >> w;
  34.     for (int i = 0; i < n; i++) {
  35.         cin >> weight[i] >> value [i];
  36.     }
  37.     for (int i = 0; i < 105; i++) {
  38.         for (int j = 0; j < 100005; j++) {
  39.             memo[i][j] = -1;
  40.         }
  41.     }
  42.     ll rez = 0;
  43.     for (int i = 0; i < 100005; i++) {
  44.         if(ks(0,i) <= w){
  45.             rez = i;
  46.         }
  47.     }
  48.     cout << rez;
  49. }
  50.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement