ABC015 D - 高橋くんの苦悩｜AtCoder - C++競プロ学習日記(仮)

題意

この問題は良くある knapsack 問題に置き換えて考えられる為、本当の題意は省略します。
与えられる変数と値は以下のように置き換えて考えます。

$W$ … knapsack の容量
$N$ … 与えられる荷物の数
$K$ … knapsack に詰めれる荷物の個数
$A_i$ … 各荷物の重さ
$B_i$ … 各荷物の価値

$N$ 個の荷物とその荷物の重さ $A_i$ と荷物の価値 $B_i$ が与えられる。
knapsack の容量 $W$ と knapsack に入る荷物の個数 $K$ が与えられるので、これらを超えないように荷物を選んだ時の価値の最大値を出力する。

考察

全探索で考えると、 $N$ 個の中から $K$ 個選んで knapsack に荷物を入れる・入れないを全て試すと $O( 2^N)$ 時間のアルゴリズムになります。制約を見てみると $1 \leq N \leq 50$ なので全探索ではとても間に合わない為、DPで考えていきます。

まず、問題を読むと今まで解いてきた易しい、かつ、典型的な knapsack と 1 点違う箇所がありました。
それは、knapsack の容量制限に加えて、荷物の個数制限がある点です。
荷物の個数を管理する引数が増えるだけなので、loop DP で書く場合は 3 次元 DP で解けば良さそうでした。

DPテーブルの定義

$dp[ i ][ j ][ k ] :=$ $i$ 番目以下の荷物から $j$ 個以下選び、重さ $k$ が $W$ を超えないように荷物を選んだ時の価値の最大値

漸化式の定義

$\begin{equation} \mathrm f(0,0,k) = 0\\ \mathrm {\rm f}(i, j, k)= \left \{ \begin{array}{l} \mathrm {\rm max}\{ {\rm dp}( i - 1, j, k ), \:{\rm dp}( i - 1, j - 1, k ), \:{\rm dp}( i - 1, j - 1, k - A_{i-1} ) + B_{i-1} \}&( j \geq A_{i-1} )\\ \mathrm {\rm max}\{ {\rm dp}( i - 1, j, k ), \:{\rm dp}( i - 1, j - 1, k ) \}&(otherwise)\\ \end{array} \right. \end{equation}$