Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- #define inf (int)1e10
- int dp[100001];
- int32_t main()
- {
- int N,W;
- cin >> N>>W;
- int price[N],wt[N];
- for(int i=0;i<N;i++)
- {
- cin>> wt[i] >> price[i];
- }
- for(int i=0;i<100001;i++)dp[i]=inf;
- dp[0]=0;
- for(int i=0;i<N;i++)
- {
- for(int j=100000-price[i];j>=0;j--)
- {
- dp[j+price[i]] = min(dp[j+price[i]],dp[j]+wt[i]);
- }
- }
- for(int i=100000;i>=0;i--)
- {
- if(dp[i]<=W)
- {
- cout<<i;
- break;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement