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}

総価値ごとに、それを達成するための最小総重量を持つ。
ここでは、達成可能な状態だけを追う。
状態は $(\text{総価値},\text{最小総重量})$ の組で表す。
（実際には、中身がほとんど $\infty$ になっている配列に入っている）

まだ品物を見ていない。
この時点では、総価値 $0$ だけを総重量 $0$ で達成できる。

{
  (0, 0)
}

$1$ 個目は重さ $3$、価値 $30$ である。
この品物を使うことで、総価値 $30$ を総重量 $3$ で達成できる。

{
  (0, 0),
  (30, 3)
}

$2$ 個目は重さ $4$、価値 $50$ である。
この品物だけを使う状態が増える。
また、$1$ 個目と組み合わせる状態も増える。

{
  (0, 0),
  (30, 3),
  (50, 4),
  (80, 7)
}

$3$ 個目は重さ $5$、価値 $60$ である。
この品物を使うことで、総価値 $60,90,110,140$ の状態が増える。

{
  (0, 0),
  (30, 3),
  (50, 4),
  (60, 5),
  (80, 7),
  (90, 8),
  (110, 9),
  (140, 12)
}

重さ制限は $8$ である。
したがって、総重量が $8$ 以下の状態だけを使える。
その中で最大の総価値は $90$ なので、答えは $90$。

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

特になし。