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
vec = [(1,2), (3,1), (9,3)]

以下では、残り容量 $W$ で $id$ 以下の荷物しか選べない場合を calc(W,id) と表現する。
calc(10,2) を求めれば答えである。

calc(10,2) を求める。
$id=2$ である荷物は、重さが $9$、価値が $3$ である。
$9\times 2-1=17$ であり、残り容量 $10$ は $9$ 以上で $17$ 未満である。
よって、calc(10,1) と calc(1,1)+3 の大きい方が答え。

calc(10,1) を求める。
$id=1$ である荷物は、重さが $3$、価値が $1$ である。
$3\times 2-1=5$ であり、残り容量 $10$ は $5$ 以上である。
よって、calc(7,0)+1 が答え。

calc(7,0) を求める。
$id=0$ である荷物は、重さが $1$、価値が $2$ である。
$1\times 2-1=1$ であり、残り容量 $7$ は $1$ 以上である。
よって、calc(6,-1)+2 が答えなのだが、calc(6,-1) は明らかに $0$ なので、答えは $2$。

さかのぼって、calc(10,1) の答えは $3$。

calc(1,1) を求める。
$id=1$ である荷物は、重さが $3$、価値が $1$ である。
$3\times 2-1=5$ であり、残り容量 $1$ は $5$ 未満である。
よって、calc(1,0) が答え。

calc(1,0) を求める。
$id=0$ である荷物は、重さが $1$、価値が $2$ である。
$1\times 2-1=1$ であり、残り容量 $1$ は $1$ 以上である。
よって、calc(0,-1)+2 が答えなのだが、calc(0,-1) は明らかに $0$ なので、答えは $2$。

さかのぼって、calc(1,1) の答えは $2$。

さかのぼって、calc(10,2) の答えは $5$。

以上より、最大値は $5$ である。

注意点

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

別解

特になし。