Untitled

mail@pastecode.io avatar
unknown
c_cpp
6 months ago
1.3 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1e5 + 7;
const int maxn1 = 1e3 + 7;
const int maxn2 = 1e2 + 7;
const ll inf  = 1e15;
const ll mod = 1e9 + 7;

#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define pb(x) push_back(x)
#define all(x) sort(x.begin() , x.end())

void dbg(){
     cerr << endl;
}

template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
ll dp[maxn2][maxn1] , w[maxn] , v[maxn];

int main(){
     ios;
     int n , W;
	 cin >> n >> W;
	 ll sum = 0;
	 for(int i = 0 ;i < n ; i++){
		cin >> w[i] >> v[i];
		sum += v[i];
	 }
	 er(sum);
	 for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < maxn ; j++)
	 		dp[i][j] = inf;

	 for(int i = 0 ; i < n ;i++)
		dp[i][0] = 0;
	 dp[0][v[0]] = w[0];	
	 for(int i = 1 ; i < n ; i++){
	 	for(int j = 0 ; j <= sum ; j++){
			if(j >= v[i]){
				dp[i][j] = min(dp[i-1][j - v[i]] + w[i] , dp[i][j]);
			}
			else
				dp[i][j] = dp[i-1][j];
		}
	 }
	 int res = 0;
	 for(int i = 0 ; i <= sum ; i++){
		if(dp[n - 1][i] <= W){
			er(n-1 , i , dp[n-1][i]);
			res = max(i , res);
		}
	 }
	 cout << res;
     return 0;
}