Advertisement
knakul853

Untitled

Jul 25th, 2020
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.60 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define inf (int)1e10
  5. int dp[100001];
  6. int32_t main()
  7. {
  8.     int N,W;
  9.    cin >> N>>W;
  10.       int price[N],wt[N];
  11.  
  12.    for(int i=0;i<N;i++)
  13.    {
  14.        cin>> wt[i] >> price[i];
  15.    }
  16.     for(int i=0;i<100001;i++)dp[i]=inf;
  17.        dp[0]=0;
  18.    for(int i=0;i<N;i++)
  19.    {
  20.       for(int j=100000-price[i];j>=0;j--)
  21.       {
  22.          dp[j+price[i]] = min(dp[j+price[i]],dp[j]+wt[i]);
  23.       }
  24.    }
  25.    
  26.    for(int i=100000;i>=0;i--)
  27.    {
  28.        if(dp[i]<=W)
  29.        {
  30.            cout<<i;
  31.            break;
  32.        }
  33.    }
  34.  
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement