#include <iostream>
#include <cstdint>
#include <tuple>
#include <algorithm>
#include <vector>
typedef std::vector<std::tuple<std::uint32_t, std::uint32_t>> TVec;
typedef std::tuple<std::uint32_t, std::uint32_t, TVec> RType;
RType MakeHoge(TVec& V){
std::uint32_t Weight = 0;
std::uint32_t W = 0;
std::vector<RType> RV;
std::uint32_t Value=0;
static const std::uint32_t MaxWeight = 20;
do {
Value = 0;
Weight = 0;
for (std::size_t i = 0; i < V.size(); i++) {
W= std::get<0>(V[i]);
if (Weight + W > MaxWeight) {
RV.push_back(std::make_tuple(Weight, Value, TVec(V.begin(), V.begin() + i)));
break;
}
Value += std::get<1>(V[i]);
Weight += W;
}
} while (std::next_permutation(V.begin(), V.end()));
std::sort(RV.begin(), RV.end(), [](auto A, auto B) {return std::isgreater(std::get<1>(A), std::get<1>(B)); });
return RV[0];
}
bool Show(RType& R) {
std::cout << std::get<0>(R) << ',' << std::get<1>(R) << std::endl;
for (auto&o : std::get<2>(R)) {
std::cout << '[' << std::get<0>(o)<< ',' << std::get<1>(o) << ']';
}
std::cout << std::endl;
return true;
}
int main() {
TVec V{//重さ、価値。
std::make_tuple(3, 5),
std::make_tuple(5, 6),
std::make_tuple(6, 3),
std::make_tuple(3, 5),
std::make_tuple(5, 9),
std::make_tuple(2, 1),
std::make_tuple(7, 5),
std::make_tuple(4, 6),
std::make_tuple(8, 3),
};
RType R;
R = MakeHoge(V);
Show(R);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGludD4KI2luY2x1ZGUgPHR1cGxlPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgoKdHlwZWRlZiBzdGQ6OnZlY3RvcjxzdGQ6OnR1cGxlPHN0ZDo6dWludDMyX3QsIHN0ZDo6dWludDMyX3Q+PiBUVmVjOwp0eXBlZGVmIHN0ZDo6dHVwbGU8c3RkOjp1aW50MzJfdCwgc3RkOjp1aW50MzJfdCwgVFZlYz4gUlR5cGU7CgpSVHlwZSBNYWtlSG9nZShUVmVjJiBWKXsKCXN0ZDo6dWludDMyX3QgV2VpZ2h0ID0gMDsKCXN0ZDo6dWludDMyX3QgVyA9IDA7CglzdGQ6OnZlY3RvcjxSVHlwZT4gUlY7CglzdGQ6OnVpbnQzMl90IFZhbHVlPTA7CglzdGF0aWMgY29uc3Qgc3RkOjp1aW50MzJfdCBNYXhXZWlnaHQgPSAyMDsKCWRvIHsKCQoJCVZhbHVlID0gMDsKCQlXZWlnaHQgPSAwOwoJCWZvciAoc3RkOjpzaXplX3QgaSA9IDA7IGkgPCBWLnNpemUoKTsgaSsrKSB7CgkJCVc9IHN0ZDo6Z2V0PDA+KFZbaV0pOwoJCQlpZiAoV2VpZ2h0ICsgVyA+IE1heFdlaWdodCkgewoJCQkJUlYucHVzaF9iYWNrKHN0ZDo6bWFrZV90dXBsZShXZWlnaHQsIFZhbHVlLCBUVmVjKFYuYmVnaW4oKSwgVi5iZWdpbigpICsgaSkpKTsKCQkJCWJyZWFrOwoJCQl9CgkJCVZhbHVlICs9IHN0ZDo6Z2V0PDE+KFZbaV0pOwoJCQlXZWlnaHQgKz0gVzsKCQl9CgkKCX0gd2hpbGUgKHN0ZDo6bmV4dF9wZXJtdXRhdGlvbihWLmJlZ2luKCksIFYuZW5kKCkpKTsKCglzdGQ6OnNvcnQoUlYuYmVnaW4oKSwgUlYuZW5kKCksIFtdKGF1dG8gQSwgYXV0byBCKSB7cmV0dXJuIHN0ZDo6aXNncmVhdGVyKHN0ZDo6Z2V0PDE+KEEpLCBzdGQ6OmdldDwxPihCKSk7IH0pOwoKCXJldHVybiBSVlswXTsKfQoKYm9vbCBTaG93KFJUeXBlJiBSKSB7CgoJc3RkOjpjb3V0IDw8IHN0ZDo6Z2V0PDA+KFIpIDw8ICcsJyA8PCBzdGQ6OmdldDwxPihSKSA8PCBzdGQ6OmVuZGw7Cglmb3IgKGF1dG8mbyA6IHN0ZDo6Z2V0PDI+KFIpKSB7CgkJc3RkOjpjb3V0IDw8ICdbJyA8PCBzdGQ6OmdldDwwPihvKTw8ICcsJyA8PCBzdGQ6OmdldDwxPihvKSA8PCAnXSc7Cgl9CglzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwoKCXJldHVybiB0cnVlOwp9CgppbnQgbWFpbigpIHsKCVRWZWMgVnsvL+mHjeOBleOAgeS+oeWApOOAggoJCXN0ZDo6bWFrZV90dXBsZSgzLCA1KSwKCQlzdGQ6Om1ha2VfdHVwbGUoNSwgNiksCgkJc3RkOjptYWtlX3R1cGxlKDYsIDMpLAoJCXN0ZDo6bWFrZV90dXBsZSgzLCA1KSwKCQlzdGQ6Om1ha2VfdHVwbGUoNSwgOSksCgkJc3RkOjptYWtlX3R1cGxlKDIsIDEpLAoJCXN0ZDo6bWFrZV90dXBsZSg3LCA1KSwKCQlzdGQ6Om1ha2VfdHVwbGUoNCwgNiksCgkJc3RkOjptYWtlX3R1cGxlKDgsIDMpLAoJfTsKCglSVHlwZSBSOwoKCVIgPSBNYWtlSG9nZShWKTsKCVNob3coUik7CgoJcmV0dXJuIDA7Cn0=