みなさんこんにちは。wakimikoです。
今回は、ナップサック問題の動的計画法を用いた解法を解説していきたいと思います。
#動的計画法
動的計画法とは一度計算した結果を保存し、再利用することで計算量を減らすテクニックのことです。
英語で「Dynamic Programming」と呼ばれることから、略してDPと呼ぶことが多いです。
What is Knapsack ?
ナップサック問題とは「価値と重さが決まっている複数の商品を容量が一定のナップサックに入れる時に、商品の価値の和を最大化しろ」という問題です。
#全探索
DPに入る前に、まずは愚直にやってみましょう。
解き方としては、それぞれの商品を「ナップサックに入れるor入れない」で分岐しながら、全探索する方法が思い浮かぶと思うので再帰を用いて実装していきます。
#include <iostream>
#include <algorithm> //maxを使うため
using namespace std;
int n, W; //nは商品の数、Wはナップサックに詰め込める容量
int v[100], w[100]; //vは商品の価値、wは商品の重さ
int knap(int i, int j); //価値の和の最大を求めるための関数
int main()
{
cin >> n >> W;
for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
cout << knap(0, W) << endl;
}
int knap(int i, int j)
{
int res;
if (i == n) { //商品がもうないので0を代入する
res = 0;
}
else if (j < w[i]) { //容量不足なので入れない処理だけをする
res = knap(i+1, j);
}
else { //入れると最大になるとは限らないので入れる時と入れない時の大きい方を取る
res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i]);
}
return (res);
}
main関数でknap関数の初めの引数をknap(0, W)としたのは、スタートを最初の商品の添字である0とし、バッグに入る残りの容量をW(まだ何も入れていないため最大)としているためです。
knap関数の第二引数を「バッグに入る残りの容量」としているので、i番目の商品を入れる処理をするときは、jからその商品の重さを引き、その後にその商品の価値を足しています。
この方法でも答えは出せますが、計算量が$ O(2^n) $であるため、$ n=25 $あたりを超えると時間がかかってしまいます。
そこで少し工夫をしてみましょう。
#メモ化再帰
初めの単純再帰のコードでは再帰で関数を呼び出している中に、引数が同じ物を複数回呼んでいます。
4 5 //n = 4, W = 5
4 2 //1つ目の商品の価値は4で、重さは2
5 2 //2つ目の商品の価値は5で、重さは2
2 1 //3つ目の商品の価値は2で、重さは1
8 3 //4つ目の商品の価値は8で、重さは3
の場合、knap関数のiとjの引数は
となります。
引数が同じなら、結果も同じになるので何回も再帰をするのは無駄です。
そこで、一回計算をしたら結果を配列に保存します。
するとその引数で計算をしているかどうかを見て、されていたら配列の値を返すだけになり、それ以降の再帰をする必要がなくなります。
#include <iostream>
#include <algorithm> //maxを使うため
#include <cstring> //memsetを使うため
using namespace std;
int n, W; //nは商品の数、Wはナップサックに詰め込める容量
int v[100], w[100]; //vは商品の価値、wは商品の重さ
int memo[101][10010]; //関数の結果を保存するための配列
int knap(int i, int j); //価値の和の最大を求めるための関数
int main()
{
cin >> n >> W;
for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
memset(memo, -1, sizeof(memo)); //memoの中身を-1で埋める
cout << knap(0, W) << endl;
}
int knap(int i, int j)
{
if (memo[i][j] >= 0) { //memoに値があればそれを返す
return (memo[i][j]);
}
int res;
if (i == n) { //商品がもうないので0を代入する
res = 0;
}
else if (j < w[i]) { //容量不足なので入れない処理だけをする
res = knap(i+1, j);
}
else { //入れると最大になるとは限らないので入れる時と入れない時の大きい方を取る
res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i]);
}
return memo[i][j] = res; //値をmemoに保存する
}
やっていることは単純で、knap関数の結果をreturnする時にmemoに保存しているだけです。
この場合だと計算量は$ O(nW) $なので、単純な再帰よりも素早く解けます。
一応これも動的計画法と言えます。（一般には「メモ化再帰」と呼ばれる）
#漸化式
「memoに値を保存する」と書きましたが、memoの値が決まる順番を見てみましょう。
先ほどのメモ化再帰の関数の最後のreturn文の前に
cout << "i :" << i << "j :" << j << " " << "res :" << res << endl;
を追加します。すると結果は、例が
4 5 //n = 4, W = 5
4 2 //1つ目の商品の価値は4で、重さは2
5 2 //2つ目の商品の価値は5で、重さは2
2 1 //3つ目の商品の価値は2で、重さは1
8 3 //4つ目の商品の価値は8で、重さは3
の時に、
i :4 j :0 res :0
i :3 j :0 res :0
i :4 j :1 res :0
i :3 j :1 res :0
i :2 j :1 res :2
i :4 j :2 res :0
i :3 j :2 res :0
i :4 j :3 res :0
i :3 j :3 res :8
i :2 j :3 res :8
i :1 j :3 res :8
i :4 j :4 res :0
i :3 j :4 res :8
i :4 j :5 res :0
i :3 j :5 res :8
i :2 j :5 res :10
i :1 j :5 res :13
i :0 j :5 res :13
13
となります。この時iとjの値の変化に注目すると、jが昇順でiは一つのjの値の中で降順に値が決まっていることがわかります。そのことから漸化式を用いて
dp[n][j] = 0\\
dp[i][j] = \left\{
\begin{array}{ll}
dp[i+1][j] & (j \lt w[i]) \\
max(dp[i+1][j], dp[i+1][j-w[i]]+v[i]) & (j \geq w[i])
\end{array}
\right.
と表すことができます。この漸化式を使ってプログラムを実装すると、次のようになります。
#include <iostream>
#include <algorithm> //maxを使うため
using namespace std;
int n, W; //nは商品の数、Wはナップサックに詰め込める容量
int v[100], w[100]; //vは商品の価値、wは商品の重さ
int dp[101][10010]; //結果を保存するための関数
int main()
{
cin >> n >> W;
for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
for (int i = n-1; i >= 0; i--) { //iは大きい方から決定されるため、iはn-1から始める
for (int j = 0; j <= W; j++) { //残りの容量を表すので、0からWまでループを回す
if (j < w[i]) {
dp[i][j] = dp[i+1][j];
}
else {
dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
}
}
}
cout << dp[0][W] << endl;
}
このように書くことで、再帰がなくなりfor文だけで解くことが出来ます。
この方法もメモ化再帰同様、動的計画法であり計算量は$ O(nW) $です。
#最後に
メモ化再帰と漸化式による解き方を紹介しましたが、どちらを選んでも基本的に大きな差はありません。
漸化式を考えるのが苦手な人はまず単純再帰でコードを書けば、そのままメモ化に移行しやすいと思います。