fork(4) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int w,n(0),f,s,max_c(0),max_w(0);
  8.  
  9. int main()
  10. {	
  11. 	cin >> w;
  12. 	//cin >> n;
  13. 	vector<int>weight,cost;
  14. 	while(cin >> f >> s){
  15. 		++n;
  16. 		weight.push_back(f);
  17. 		cost.push_back(s);
  18. 	}
  19. 	//for(int i = 0;i<n;++i){       
  20. 	//	cin >> f >> s;
  21. 	//	weight.push_back(f);
  22. 	//	cost.push_back(s);
  23. 	//}
  24. 	vector<vector<int>>matrix(n+1);
  25. 	for(int i = 0;i<=n;++i)matrix[i].resize(w+1);
  26. 	for(int i = 1;i<=n;++i){
  27. 		for(int j = 1;j<=w;++j)if(weight[i-1] <= j){
  28. 			matrix[i][j] = max(matrix[i-1][j],matrix[i-1][j-weight[i-1]] + cost[i-1]);
  29. 		} else matrix[i][j] = matrix[i-1][j];
  30. 	}
  31. 	vector<int>answer;
  32. 	for(int i = n;;){
  33. 		for(int j = w;;){
  34. 			if(!matrix[i][j])break;
  35. 			if(matrix[i][j] != matrix[i-1][j]){
  36. 				answer.push_back(i);
  37. 				max_c += cost[i-1];
  38. 				max_w += weight[i-1];
  39. 				j -= weight[i-1];
  40. 			} 
  41. 			--i;
  42. 		}
  43. 		break;
  44. 	}
  45. 	sort(answer.begin(),answer.end());
  46. 	cout << max_w << ' ' << max_c << '\n';
  47. 	for(int i = 0;i<answer.size();++i)cout << answer[i] << ' ';
  48.  
  49. 	return 0;
  50. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
13 
3 1
4 6
5 4
8 7
9 6
stdout
copy 
12 13
2 4
https://ideone.com/pqt2eS
language:
C++14 (gcc 8.3)
created:
6 years 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!