No.032 D

制約ごとに解法を変える.

$N \leq 30$

半分全探索を使う.

荷物を半分に分ける. 前半, 後半ともにすべての荷物の組み合わせで重量と価値を計算する.

後半の方は重量でソートし, その重量以下の場合に得られる最大価値を計算しておく.

前半の組み合わせごとに後半でどの重量まで入れられるかを二分探索で探し, 前半の組み合わせでの価値と後半の最大価値を足したものの最大値を求める.

$w_i \leq 1000$

動的計画法を使う. ナップザック問題の典型である.

$\sum w_i \leq 200000$ なのでループ回数は最大 $4 \times 10^7$ となり, おそらく間に合う.

$v_i \leq 1000$

これも動的計画法を使う.

上記の動的計画法が, “$i$ 個までの荷物を見たときに重量が $j$ となる最大価値” をメモしていたのに対し, この制約では “$i$ 個までの荷物を見たときに価値が $j$ となる最小重量” をメモする.