ARC223 A - Unusual-Constraint Knapsack

考え方

ナップサック問題。
一般的な制約での解き方はわかっておらず、おそらく高速な解き方は存在しない（NP完全問題）。

$N \leq 20$ くらいならbit全探索、$N \leq 40$ くらいなら半分全列挙で間に合うが、今回は $N \leq 60$。
$W$ や $\Sigma v$ が小さければ動的計画法で解けるが、今回はそれも無理。
ということで、$w$ に関する特殊な制約を利用して、今回ならではの解法を考えなければならない。

これは、貪欲法で枝刈りをしながら重い荷物から順に採用するか否かを深さ優先探索をすればよい。
すなわち、残り容量 $W$ の状況で重さ $x$ の荷物を採用するか否かは、以下で決定できる。

• $W\geq 2x-1$ である場合、残りを全部採用可能なので、貪欲法により採用の方だけ進む。
• $x\leq W<2x-1$ である場合、採用する場合としない場合と両方あり得るので、両方に進む。
• $W<x$ である場合、採用不可能なので、不採用の方だけ進む。

真ん中のパターンから不採用の方に進んだ場合、残りの荷物が全て入るだけの容量が残っている。
この場合、この枝は $O(\text{残り荷物数})$ で求まる。
したがって、最大に分岐しても $O(N^2)$ で求まる。
累積和等を使えば $O(N)$ にすることもできるが、$N\leq 60$ なのでそこまでする意味は薄い。

入力例1での動作

$1$ つ目のテストケースのみ考える。

入力を受け取る。

n: 3
w: 10
items:
(1, 2)
(3, 1)
(9, 3)

重い荷物から順に考える。

まず、重さ $9$、価値 $3$ の荷物を見る。
残り容量は $10$ で、$9\leq10<2\times9-1=17$ である。
したがって、この荷物を採用する場合と採用しない場合の両方を調べる。

採用しない場合、残り容量は $10$ のままである。
次の荷物は重さ $3$、価値 $1$ で、$10\geq2\times3-1=5$ なので採用する。
残り容量は $7$ となる。
最後の重さ $1$、価値 $2$ の荷物も採用できるので、価値の合計は $3$ となる。

重さ $9$ の荷物を採用する場合、残り容量は $1$、価値の合計は $3$ となる。
重さ $3$ の荷物は採用できない。
最後の重さ $1$、価値 $2$ の荷物は採用できるので、価値の合計は $5$ となる。

$3$ と $5$ の大きい方を選び、答えは $5$ となる。

注意点

答えや重さは、int 型からはみ出る。
long long 型を用いること。

別解

特になし。