fork download
  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
stdin
Standard input is empty
stdout
20,31
[4,6][5,9][3,5][3,5][5,6]