個数制限なしナップザック問題を自分なりにかみ砕く

記事の概要

個数制限なしナップザック問題について、僕が詰まったところを自分なりにかみ砕きながら解説します。僕はまだ茶色コーダーなので、比較的多くの人の目線に寄り添うことができると思います。

なお、この記事は通常のナップザック問題の解法を理解していることを前提としています。通常のナップザック問題の解法が知りたい方は、他の方の記事を参照してみて下さい。

けんちょんさんの記事: 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～

この記事を書くにあたって、「プログラミングコンテストチャレンジブック [第2版]」(通称「蟻本」)の58-59ページを参考にしました。

問題の概要

AOJから問題を取ってきました。問題を以下に要約します。
AOJ DPL_1_C ナップザック問題

価値が$v_i$、重さが$w_i$である$N$種類の品物と、容量$W$のナップザックがある。
容量$W$を超えないように品物を詰め、価値の合計を最大化したい。価値の最大値はいくらか。
ただし、同じ種類の品物をいくつでも選ぶことができる。

制約

• $1 \le N \le 100$
• $1 \le v_i \le 1000$
• $1 \le w_i \le 1000$
• $1 \le W \le 10000$

解法

DPテーブルは通常のナップザック問題と大差ありません。
$$
dp[i][j] = i番目の品物までを使い、重さj以下になるように詰めたときの価値の最大値
$$

問題はDPテーブルの更新です。通常のナップザック問題では、$i$番目の品物を使う/使わないの2通りを考えればよく、更新が簡単でした。しかし、今回は個数制限がないため、「使わない/1個使う/2個使う/.../k個使う」と、無数の選択肢があります。

まずは愚直にDPテーブルの更新を考えてみます。

$$
dp[i+1][j] = \max(dp[i][j], dp[i][j-k \times v[i]] + k \times v[i]) \quad (0 \le k \land k \times w[i] \le j)
$$

$k=0$のときで、その品物を選ばない場合も考えられています。計算量を見積もると、$i$について$n$通り、$j$について$W$通り、kについて最悪$W$通りあるので、$O(nW^2)$となります。これでは間に合わないので、工夫を考えます。

このDPを実装すると以下の3重ループになります。

• $i$(品物の番号)のループ: 品物番号のインデックスをループする。
• $j$(重さ)のループ: 重さのインデックスをループする。
• $k$(個数)のループ: 重さのインデックス をループする。

この中で削れるループは$k$のループです。なぜなら、$j$のループが回っている時点で、今までにあり得る重さ($\lt j$)をすべて考えているからです。先ほど$k$を「個数のループ」と題しましたが、実情として$k$は重さに関するインデックスにかかわっています。

$j$が増えるたびに詰められる品物$i$の数$k$は増加します。よって、$j$の更新とともに、品物$i$が新しく1個詰められるようになったら詰めていけば、2重ループで更新できます。

数式を使って示すこともできます。先ほどの漸化式の右辺について考えると(kの最大値についての条件は省略します)、

\begin{align}
\max(dp[i][j], dp[i][j-k \times v[i]] + k \times v[i] \mid k \ge 0) &= \max(dp[i][j], \max(dp[i][j-k \times w[i]]+ k \times v[i] \mid 1 \le k)) \quad \text{($k=0$の場合を分離した)} \\
&= \max(dp[i][j], \overbrace{\max(dp[i][(j - w[i]) - k \times w[i]] + k \times v[i] \mid 0 \le k)}^\text{そのまま $dp[i+1][j-w[i]]$ の定義と一致する。} + v[i]) \quad \text{($k \ge 1$の場合を、$k \ge 0$になるように変形した。)} \\
&= \max(dp[i][j], dp[i+1][j-w[i]]+v[i])
\end{align}

このように$k$を消去することができます。この数式に関しては蟻本のものをそのまま持ってきて、僕が説明を加えました。「1行目はどうやったら思いつくねん」って話ですが、そもそもdpが漸化式の考え方を用いて計算量を削減する考え方である以上、$n$項目と$n-1$項目の関係を使おうとして分離する発想が出てくるのは無理もないのかなと思います。

結果的に以下のコードを提出することで解くことができます。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i=0; i<(int)(n); i++)
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

int dp[101][10001];

int main(void) {
    int n, W; cin >> n >> W;

    vector<int> v(n);
    vector<int> w(n);
    rep(i, n) {
        cin >> v[i] >> w[i];
    }

    rep(i, n) {
        rep(j, W+1) {
            chmax(dp[i+1][j], dp[i][j]);
            if(j - w[i] >= 0) {
                chmax(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
            }
        }
    }

    cout << dp[n][W] << endl;
    return 0;
}