Advertisement
Josif_tepe

Untitled

Apr 13th, 2022
976
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long n;
  6. long long w;
  7. vector<pair<long long,long long>>v;
  8. long long dp[100005][105];
  9.  
  10. long long f(long long k, long long idx)
  11. {
  12.     if(k==0)
  13.     {
  14.         return 0;
  15.     }
  16.     if(idx==n)
  17.     {
  18.         return 1e16;
  19.     }
  20.     if(dp[k][idx]!=-1)
  21.     {
  22.         return dp[k][idx];
  23.     }
  24.     long long rez=1e16;
  25.     if(k >= v[idx].second)
  26.         rez=min(rez, f(k-v[idx].second,idx+1)+v[idx].first);///w
  27.     rez=min(rez, f(k,idx+1));
  28.     return dp[k][idx]=rez;
  29. }
  30.  
  31. int main()
  32. {
  33.     cin>>n>>w;
  34.     long long x,y;
  35.     memset(dp,-1,sizeof dp);
  36.     for(long long i=0;i<n;i++)
  37.     {
  38.         cin>>x>>y;
  39.         v.push_back({x,y});
  40.     }
  41.     for(long long i=100000;i>=0;i--)
  42.     {
  43.         if(f(i,0)<=w)
  44.         {
  45.             cout<<i;
  46.             break;
  47.         }
  48.     }
  49.     return 0;
  50. }
  51.  
Advertisement
RAW Paste Data Copied
Advertisement