fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main() {
  6. 	int n,W; cin>>n>>W;
  7. 	vector <int> v(n),w(n);
  8.  
  9. 	for(int i=0; i<n; i++){
  10. 		cin>>v[i]>>w[i];
  11. 	}
  12. 	int dp[101][100005];
  13. 	// memset(dp, 0, sizeof(dp));
  14. 	for (int i=0; i<101; i++){
  15. 		for (int j=0; j<100005; j++){
  16. 			dp[i][j] = 1e9;
  17. 		}
  18. 	}
  19.  
  20. 	dp[0][0] = 0;
  21.  
  22. 	for (int i=0; i<n; i++){
  23. 		for (int j=0; j<100002; j++){
  24. 			if (j+v[i] < 100004){
  25. 				dp[i+1][j+v[i]] = min(dp[i][j]+w[i], dp[i+1][j+v[i]]);
  26. 				dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
  27. 			}
  28. 		}
  29. 	}
  30. 	int ans = 0;
  31. 	for (int j=0; j<100004; j++){
  32. 		if (dp[n][j] <= W){
  33. 			ans = max(ans, j);
  34. 		}
  35. 	}
  36.  
  37. 	cout<<ans<<endl;
  38. 	return 0;
  39. }
Success #stdin #stdout 0.02s 42980KB
comments (?)
stdin
copy 
3 8
3 30
4 50
5 60
stdout
copy 
0
https://ideone.com/E4sQ60
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!