概要 ナップザック問題を分岐限定法で爆速($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$が少ない場合、半分全
![Atcoder ABC32 D - ナップザック問題を分岐限定法で爆速で解く - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/cb5414a00e42bba6cf19131e9acf65a4ea117871/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-412672c5f0600ab9a64263b751f1bc81.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9QXRjb2RlciUyMEFCQzMyJTIwRCUyMC0lMjAlRTMlODMlOEElRTMlODMlODMlRTMlODMlOTclRTMlODIlQjYlRTMlODMlODMlRTMlODIlQUYlRTUlOTUlOEYlRTklQTElOEMlRTMlODIlOTIlRTUlODglODYlRTUlQjIlOTAlRTklOTklOTAlRTUlQUUlOUElRTYlQjMlOTUlRTMlODElQTclRTclODglODYlRTklODAlOUYlRTMlODElQTclRTglQTclQTMlRTMlODElOEYmdHh0LWFsaWduPWxlZnQlMkN0b3AmdHh0LWNvbG9yPSUyMzIxMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZzPTk0N2FkMWRkNDUxOTdmMzc4NjFiZjBlN2Y4YzFlMmRl%26mark-x%3D142%26mark-y%3D57%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9NzcwJnR4dD0lNDBoYW1rbyZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9NDcwNmFhNzNjODRjODVmMGU2OTkzMjZmY2U4ZGMwOTE%26blend-x%3D142%26blend-y%3D486%26blend-mode%3Dnormal%26s%3D56b71d582744387f0a9f0929f54ae7e1)