Atcoder ABC32 D - ナップザック問題を分岐限定法で爆速で解く - Qiita

概要 ナップザック問題を分岐限定法で爆速（$n<2000, v_i<10^{12}, w_i<10^{12}$を$1$秒）で解きます。実行時間ベースで今のところ3位です。提出はこちら これは競技プログラミング 解説 Advent Calendar 2017の16日目の記事です。 ナップザック問題 ナップザック問題とは、重さ制約$W$と$n$個の荷物価値ペア($v_i, w_i$)が与えられて、$\displaystyle \max_{S \in 2^n, \sum_S w_i \le W} \sum_S v_i$を求める問題です。Atcoder ABC 32 - D - ナップザック問題は、様々な$n$, $v_i$, $w_i$の制約のもとで、この問題を解くという趣旨でした。 この問題は、以下の3つのDP解を、テストケースごとに作成することで通すことができます（提出）。 (1) $n$が