EDPC D - Knapsack 1

考え方

ABCでいうと、D問題級。

重さ制限がある中で、価値の合計を最大化する問題。
典型的な $0/1$ ナップサック問題である。

dp[j] を、総重量 $j$ 以下での最大価値とする。
各品物について、使う場合と使わない場合を比較しながら DP テーブルを更新する。

ただし、同じ品物を $2$ 回以上使わないようにするため、dp は重い方から更新する。
詳しくは「ナップサック問題」の記事参照。

計算量は $O(NW)$。

入力例1での動作

入力を受け取る。

n: 3
m: 8
w: {3, 4, 5}
v: {30, 50, 60}

重さ上限ごとに、得られる価値の最大値を持つ。
何も品物を見ていない間は、どの重さ上限でも価値は $0$ である。

$1$ 個目は重さ $3$、価値 $30$ である。
重さ上限が $3$ 以上なら、この品物を入れられる。
そのため、価値の最大値は $30$ になる。

$2$ 個目は重さ $4$、価値 $50$ である。
例えば、重さ上限 $8$ の場合を考える。
それまでの最大値は $30$ である。
$1$ 個目と $2$ 個目を入れると、価値は $30+50=80$ になる。
よって、最大値を $80$ に更新する。

$3$ 個目は重さ $5$、価値 $60$ である。
再び、重さ上限 $8$ の場合を考える。
それまでの最大値は $80$ である。
$1$ 個目と $3$ 個目を入れると、価値は $30+60=90$ になる。
よって、最大値を $90$ に更新する。

各品物まで処理した時点での状態は次のようになる。

重さ上限 $8$ での最大価値 $90$ が答え。

注意点

価値の和は、int 型からはみ出る。
long long 型を用いること。

別解

特になし。