Advertisement
Josif_tepe

Untitled

Nov 3rd, 2021
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.74 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. int dp[100000];
  6. int n;
  7. vector<int>w1;
  8. vector<int>v1;
  9. int rec(int weight1){
  10.     if(weight1==0){
  11.         return 0;
  12.     }
  13.     if(dp[weight1]!=-1){
  14.         return(dp[weight1]);
  15.     }
  16.     int result=0;
  17.     for(int j=0; j<n; j++){
  18.         if(weight1-w1[j]>=0){
  19.             result=max(result, rec(weight1-w1[j])+v1[j]);
  20.         }
  21.     }
  22.     dp[weight1]=result;
  23.     return result;
  24. }
  25. int main()
  26. {
  27.  
  28.     int w;
  29.     cin>>n>>w;
  30.     for(int i=0; i<n; i++){
  31.         int a, b;
  32.         cin>>a>>b;
  33.         w1.push_back(a);
  34.         v1.push_back(b);
  35.  
  36.  
  37.     }
  38.  
  39.     for(int i=0; i<100000; i++){
  40.      dp[i]=-1;
  41.     }
  42.  
  43.     cout<<rec(w);
  44.  
  45.     return 0;
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement