fork download
copy 
  1. #include <iostream>
  2. #include <cstdint>
  3. #include <tuple>
  4. #include <algorithm>
  5. #include <vector>
  6.  
  7. typedef std::vector<std::tuple<std::uint32_t, std::uint32_t>> TVec;
  8. typedef std::tuple<std::uint32_t, std::uint32_t, TVec> RType;
  9.  
  10. RType MakeHoge(TVec& V){
  11. 	std::uint32_t Weight = 0;
  12. 	std::uint32_t W = 0;
  13. 	std::vector<RType> RV;
  14. 	std::uint32_t Value=0;
  15. 	static const std::uint32_t MaxWeight = 20;
  16. 	do {
  17.  
  18. 		Value = 0;
  19. 		Weight = 0;
  20. 		for (std::size_t i = 0; i < V.size(); i++) {
  21. 			W= std::get<0>(V[i]);
  22. 			if (Weight + W > MaxWeight) {
  23. 				RV.push_back(std::make_tuple(Weight, Value, TVec(V.begin(), V.begin() + i)));
  24. 				break;
  25. 			}
  26. 			Value += std::get<1>(V[i]);
  27. 			Weight += W;
  28. 		}
  29.  
  30. 	} while (std::next_permutation(V.begin(), V.end()));
  31.  
  32. 	std::sort(RV.begin(), RV.end(), [](auto A, auto B) {return std::isgreater(std::get<1>(A), std::get<1>(B)); });
  33.  
  34. 	return RV[0];
  35. }
  36.  
  37. bool Show(RType& R) {
  38.  
  39. 	std::cout << std::get<0>(R) << ',' << std::get<1>(R) << std::endl;
  40. 	for (auto&o : std::get<2>(R)) {
  41. 		std::cout << '[' << std::get<0>(o)<< ',' << std::get<1>(o) << ']';
  42. 	}
  43. 	std::cout << std::endl;
  44.  
  45. 	return true;
  46. }
  47.  
  48. int main() {
  49. 	TVec V{//重さ、価値。
  50. 		std::make_tuple(3, 5),
  51. 		std::make_tuple(5, 6),
  52. 		std::make_tuple(6, 3),
  53. 		std::make_tuple(3, 5),
  54. 		std::make_tuple(5, 9),
  55. 		std::make_tuple(2, 1),
  56. 		std::make_tuple(7, 5),
  57. 		std::make_tuple(4, 6),
  58. 		std::make_tuple(8, 3),
  59. 	};
  60.  
  61. 	RType R;
  62.  
  63. 	R = MakeHoge(V);
  64. 	Show(R);
  65.  
  66. 	return 0;
  67. }
Success #stdin #stdout 0.42s 8680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
20,31
[4,6][5,9][3,5][3,5][5,6]
https://ideone.com/rIBT6g
language:
C++14 (gcc 8.3)
created:
8 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!