Top

動的計画法が超苦手な人はきっと01ナップサックも解いたことがないんだ。
というわけで、この問題を考えてみておくれ。
「01ナップサック」
$N$ 個の品物にはそれぞれ「重さ($w_{i}$) 」と「価値($v_{i}$)」というパラメータがあります。
今、これらの品物からいくつか選ぼうとします。
重さの合計が $W$ 以下になっていれば、どう選んでもいいです。
価値が最大にできる選び方にしたとき、その価値を求めてください。

とりあえず、$N$ は $10$ ぐらいまででいいや。$w_{i}$ とか $v_{i}$ も $100$ ぐらいまでにしておく。$W$ は $1{,}000$ ぐらいまでにしておこう。(テストケースを用意したぜ！)
再帰を使った深さ優先探索で書けるかい? ＞(ΦωΦ)

(ΦωΦ)＜コード 1-1 
#include <iostream>
#include <algorithm>
using namespace std;

int N, W;
vector<int> w, v;

// 今 i 番目の品物を目にして取ろうか取るまいか悩んでいる状態。
// これまで(つまりi-1番目まで)に選んだ品物の重さの合計は weight で、価値の合計の最大は value。
int rec(int i, int weight, int value) {
  if(i == N) { return value; }
  if(weight + w[i] > W) {
    return rec(i+1, weight, value);
  } else {
    return max(rec(i+1, weight+w[i], value+v[i]),
               rec(i+1, weight,      value));
  }
}

int main(void) {
  scanf("%d", &N);
  w.assign(N, 0);
  v.assign(N, 0);
  for(int i=0; i<N; i++) { scanf("%d", &w[i]); }
  for(int i=0; i<N; i++) { scanf("%d", &v[i]); }
  scanf("%d", &W);
  int res = rec(0, 0, 0);
  printf("%d\n", res);
  return 0;
}

(ΦωΦ)＜もしこれが書けなかったのなら、動的計画法うんぬんより先にこれを書けるようになるべきだ！

---
さて、$N$ が $100$ になっても動くプログラムにしよう。 $N$ が $100$ だから $W$ は $10{,}000$ ぐらいまでにしておこうか。(これもテストケースを用意したぜ！)
"コード 1-1" は「 $N = 100$ のときには返事が返って来るまでとてつもなく時間がかかる」というのが、プログラムを見ただけで分かるかい? ＞(ΦωΦ)
理由はこのプログラムの計算量が $O(2^{N})$ だからだね。
$N$ 個の品物それぞれを「取る」か「取らない」かというのを全部試すので、$2^{N}$ になるんだね。

---
"コード 1-1" には引数に無駄がある、というのが分かるだろうか。
$i$ 番目を目にしている状態で、重さの合計が $weight$ だったとき、価値の合計の最大値 $value$ は一意に決まるのである。
だから引数に $value$ はいらない。

こんな疑問があるかもしれない。

(？ω？)＜$i$ 番目を目にしているということは、$i-1$ 番目まで見終わってるんだよね？
そのときの重さの合計が $weight$ だったとしても、価値の合計は一意に決まらないんじゃないかな？

この疑問は正しい。しかし、今気にしないといけないのは、価値の合計の最大値だけなのだ！
例えば、今 $5$ 番目を目にしていて、 $0$ 番目と $1$ 番目と $3$ 番目で重さの合計が $weight$ になるかもしれない。$2$ 番目と $4$ 番目でも重さの合計が $weight$ になるかもしれない。そして、この2つの選び方で、価値の合計が同じかどうかは分からない。
しかし、こんなふうに品物の選び方に複数の方法があったとしても、その中の価値の合計の "最大値" というのはひとつに決まるのである。

価値の合計が最大になる選び方が複数あったとしても、そのときの価値の合計の最大値は同じであり(最大だからね！)、しかもその値だけが知りたいのであって、そのときの選び方には興味がないのである。

---
なので、"コード 1-1"から引数 $value$ を無くしてみよう。
とは言っても、コードの中で $value$ を返してるところがあるので、そう単純にできるものではない。

ここでいわゆる「DPテーブル」が出てくる。
$i$ と $weight$ が決まれば $value$ が決まるのだから、$i$ と $weight$ という2つのパラメータを持った dp という配列を使って $value$ を表現するのである。
解説ブログとかでよく見ると思うけど、こんなの↓
dp[ $i$ 番目を目にしている状態で][重さの合計が $weight$ だったとき] = 価値の合計の最大値が $value$

これを使って"コード 1-1"を書き直してみなー。

(ΦωΦ)＜コード 1-2
#include <iostream>
#include <algorithm>
using namespace std;

int N, W;
vector<int> w, v;
vector<vector<int>> dp;

int rec(int i, int weight) {
  if(i == N) { return dp[i][weight]; }
  if(weight + w[i] > W) {
    dp[i][weight] = rec(i+1, weight);
    return dp[i][weight];
  } else {
    dp[i][weight] = max(rec(i+1, weight+w[i]) + v[i],
                        rec(i+1, weight));
    return dp[i][weight];
  }
}

int main(void) {
  scanf("%d", &N);
  w.assign(N, 0);
  v.assign(N, 0);
  for(int i=0; i<N; i++) { scanf("%d", &w[i]); }
  for(int i=0; i<N; i++) { scanf("%d", &v[i]); }
  scanf("%d", &W);
  dp.assign(110, vector<int>(10010, 0));
  int res = rec(0, 0);
  printf("%d\n", res);
  return 0;
}

書けたー？
ちょっとコードを見ておこう。
mainの中でdpテーブルを初期化している(28行目)。
$N$ が $100$ まで、$W$ が $10{,}000$ までだけれど、配列外アクセスとかややこしいからちょっと大きめに取ってる。
$value$ だったものは $i$ と $weight$ を使った変数 dp であらわすことにしたから、12行目や15,16行目はこんな感じになる。
15,16行目がちょっと難しいかもしれないが、関数 rec が返すものは "価値" の最大値だと意識することが重要だと思う。

---
残念なことに、これで速くなったわけではない。しかし速くする準備は整ったのである！
速くするにはどうすればいいか。さっきから言ってるが、$i$ と $weight$ が決まればそのときの $value$ (=dp[$i$][$weight$]) が決まるのである。
だから一度見たところは再帰を辿らなければいい。

一度見たという判断はどうすればいいか。
最初dpテーブルは全部 $0$ で初期化した。しかし、$i$ と $weight$ によっていったん確定した dp[$i$][$weight$] は、$0$ より大きい値になるのである。
これを使わない手はない。

(ΦωΦ)＜コード 1-3 
#include <iostream>
#include <algorithm>
using namespace std;

int N, W;
vector<int> w, v;
vector<vector<int>> dp;

int rec(int i, int weight) {
  if(dp[i][weight] > 0) { return dp[i][weight]; } // "コード 1-2"からこの1行だけ足しました＞(ΦωΦ)
  if(i == N) { return dp[i][weight]; }
  if(weight + w[i] > W) {
    dp[i][weight] = rec(i+1, weight);
    return dp[i][weight];
  } else {
    dp[i][weight] = max(rec(i+1, weight+w[i]) + v[i],
                        rec(i+1, weight));
    return dp[i][weight];
  }
}

int main(void) {
  scanf("%d", &N);
  w.assign(N, 0);
  v.assign(N, 0);
  for(int i=0; i<N; i++) { scanf("%d", &w[i]); }
  for(int i=0; i<N; i++) { scanf("%d", &v[i]); }
  scanf("%d", &W);
  dp.assign(110, vector<int>(10010, 0));
  int res = rec(0, 0);
  printf("%d\n", res);
  return 0;
}

これでメモ化再帰が書けた。

最後に補足。
    dp[i][weight] = rec(i+1, weight);
    return dp[i][weight];
は、C++とかJavaだったら
    return dp[i][weight] = rec(i+1, weight);
と書けるよ。Pythonはできないので上の書き方で済ませたり@memoizeしたりします。

とりあえずここまでできれば、動的計画法で解いてほしい問題も解けてるし、今日のところはいいんじゃないかな。

(ΦωΦ)＜つづく