EDPC E - Knapsack 2

ナップサック2

考え方

ABCでいうと、D問題級。

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

ただし、今回は重さ制限 $W$ が非常に大きい。
そのため、D 問題のように重さを DP テーブルの添字にすると間に合わない。

そこで、価値の方を DP テーブルの添字にする。
dp[j] を、総価値 $j$ での最小総重量とする。

各品物について、使う場合と使わない場合を比較しながら DP テーブルを更新する。
ただし、同じ品物を $2$ 回以上使わないようにするため、dp は価値が大きい方から更新する。

最後に、最小総重量が $W$ 以下である価値のうち、最も大きいものを探せばよい。
詳しくは「ナップサック問題」の記事参照。

計算量は $O(N\sum V)$。

入力を受け取る。

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

価値合計は $30+50+60=140$ なので、今回は dp[0] から dp[140] までを用意する。
dp[j] を、総価値 $j$ での最小総重量とする。

何も品物を見ていない状態では、総価値 $0$ だけが重さ $0$ で達成できる。
それ以外は INF で初期化する。

dp[0]: 0
その他: INF

$1$ 個目の品物 $(w,v)=(3,30)$ を見る。
この品物を使うと、総価値 $30$ を総重量 $3$ で達成できる。

dp[0] : 0
dp[30]: 3
その他: INF

$2$ 個目の品物 $(w,v)=(4,50)$ を見る。
この品物だけを使うと、総価値 $50$ を総重量 $4$ で達成できる。
また、$1$ 個目と $2$ 個目を両方使うと、総価値 $80$ を総重量 $7$ で達成できる。

dp[0] : 0
dp[30]: 3
dp[50]: 4
dp[80]: 7
その他: INF

$3$ 個目の品物 $(w,v)=(5,60)$ を見る。
この品物を使うことで、いくつかの総価値を更新できる。

dp[0]  : 0
dp[30] : 3
dp[50] : 4
dp[60] : 5
dp[80] : 7
dp[90] : 8
dp[110]: 9
dp[140]: 12
その他: INF

重さ制限は $8$ なので、最小総重量が $8$ 以下であるものだけが使える。
その中で最も大きい総価値は $90$ なので、答えは $90$。

総重量は、int 型からはみ出る。
long long 型を用いること。

特になし。