日記

のみろぐ

主に競プロ日記です

DPL_1_C「ナップザック問題」

DPL_1_C「ナップザック問題

考察

  • DPに使いそうな値を考える
    • 今回は01ナップザックみたいに何個目まで選んだかという情報は必要無い
    • 価値と重さが分ればいいかなーってなる
  • 価値と重さだけわかれば良いので1次元のDPでできそう
  • 同じ種類の荷物は何個でも使うことができるため、コイン問題のように考えることができる。
  • なので、コイン問題みたいに解けばできそう
  • 考察終了!


解法

手順

f:id:nomikura:20180616055444p:plain:w300

  1. 上図のようなDPテーブルを作る
  2. DPテーブルを$0$で初期化する
  3. 漸化式を立てて、そのコードを書く

漸化式

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


コード

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

const int INF = 1e8;

int N, W;
int v[111], w[111];
int dp[11111];

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; i++) { cin >> v[i] >> w[i]; }

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

    cout << dp[W] << endl;

    return 0;
}


要点

  • DPに必要な情報が何かを考えること。
    • このとき考えるのは答えを求めるのに必要最低限の情報だけにする。
  • コイン問題に帰着できることに気がつくこと。

感想

  • 1次元のDPはだいたいコイン問題に帰着できる説が浮上しつつある(ホンマか?
  • なんとなくで解いたのでまだ確信が持てないという...