日記

のみろぐ

主に競プロ日記です

DPL_1_B「0-1 ナップザック問題」

DPL_1_B「0-1 ナップザック問題」

解法

f:id:nomikura:20180616043824p:plain:w450

  1. 上図のようなDPテーブルを用意する
  2. テーブルをすべて$0$で初期化する(グローバルに宣言していれば初期化する必要は無い)
  3. 漸化式を立て、それをコードとして書く


漸化式

$$ dp[i][j] = \left\{ \begin{array}{ll} max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) & (j \geq w[i]) \\ dp[i-1][j] & (j \lt w[i]) \end{array} \right. $$


部分的に見る

f:id:nomikura:20180616055904p:plain:w500

  • いきなり全体的なことを考えると頭が爆発するので一部分に注目してみる
  • $dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]+v[i]])$という式について
    • maxの左側は$v[i]$を選ばない場合を表す
    • maxの右側は$v[i]$を選ぶ場合を表す
    • 両方の値を比較して大きい方が$dp[i][j]$になる


コード

#include <bits/stdc++.h>
using namespace std;

int N, W;
int v[111], w[111];
int dp[111][11111]; // dp[i][j]: 重さ制限jで個数iまで見たときの最大の価値

int main() {
    // 入力
    cin >> N >> W;
    // インデックスを1つずらしている
    for (int i = 0; i < N; i++) { cin >> v[i+1] >> w[i+1]; }

    // DP
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][W] << endl;

    return 0;
}
  • 便宜上、入力の際に重さと価値のインデックスを1つ先へずらした
  • 集めるDPはdp[i][j] = 遷移元の形にしたい。
  • 読みにくいかもだけど、書き方は他の問題も見て検討する


要点

  • $dp[i][j]$を求めるとき、$dp[i-1][W]$までは既に求められていることが前提となっている。
  • なので、$dp[i][j]$を求めたいときに、それ以前がどんな状態であるかは考える必要が無い。
    • これを頭に置いておかないと考えることが多くて頭が爆発する