分枝限定法に関するカテゴリーです

AtCoder,分枝限定法,深さ優先探索

問題方針

整数計画法である 0-1 ナップサック問題を線形計画法で解くことを考えます。線形計画法では、重さ当たりの価値が大きいものから取っていけば良いです。ここで、荷物を重さ当たりの価値の降順になるように並び替えます。

深さ ...

AtCoder,ビット全探索,二分探索,分枝限定法,半分全列挙

問題方針半分全列挙

\( n = \min(20, N) \) として、問題を \( n \) と \( N – n \) 個に分けて考えます。前半の問題の集合を \( A \) とし、後半を \( B \) とします。\( ...