ナップサック問題の半分全列挙をO(2^{n / 2})で解く
少し話題になったので、自分のメモも兼ねて
2ⁿ パターン列挙してソートする Θ(2ⁿ log(2ⁿ)) = Θ(n2ⁿ) と比べて n が落ちる
— 熨斗袋 (@noshi91) June 13, 2020
半分全列挙でこれを使って、最後の合わせるパートも尺取で n を落とせるのでオーダーが落ちます
方針はこれです。ちなみになんですが、ソートされた配列をソートしたままmergeするのに、C++はstd::mergeがあるのでこれを使うと結構楽にかけます。
実装が分からないよって人は参考にしてみてください。
実装例
なのはassertしてるので、分かりにくいですが、4msぐらいでかなり早いですね。
