EDPC D - Knapsack 1

ナップサック1

考え方

ABCでいうと、D問題級。

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

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

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

計算量は $O(NW)$。

入力を受け取る。

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

dp[j] を、総重量 $j$ 以下での最大価値とする。
今回は dp[0] から dp[8] までを用意する。

何も品物を見ていない状態では、どの重さ上限でも価値は $0$ である。

dp: {0, 0, 0, 0, 0, 0, 0, 0, 0}

$1$ 個目の品物 $(w,v)=(3,30)$ を見る。
重さ上限 $3$ 以上であれば、この品物を入れられる。

dp: {0, 0, 0, 30, 30, 30, 30, 30, 30}

$2$ 個目の品物 $(w,v)=(4,50)$ を見る。
重さ上限 $4$ 以上であれば、この品物を入れられる。

例えば、重さ上限 $8$ では、すでにある価値 $30$ と、
$1$ 個目と $2$ 個目を両方入れた価値 $30+50=80$ を比較する。
よって、dp[8] は $80$ になる。

dp: {0, 0, 0, 30, 50, 50, 50, 80, 80}

$3$ 個目の品物 $(w,v)=(5,60)$ を見る。
重さ上限 $5$ 以上であれば、この品物を入れられる。

例えば、重さ上限 $8$ では、すでにある価値 $80$ と、
$1$ 個目と $3$ 個目を入れた価値 $30+60=90$ を比較する。
よって、dp[8] は $90$ になる。

dp: {0, 0, 0, 30, 50, 60, 60, 80, 90}

DP テーブルの一番後ろの値、つまり dp[8] の $90$ が答え。

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

特になし。