【Java】ナップサック問題(knapsack)[動的計画法]

ヽ｜∵｜ゝ(Fantom) の開発blog？ホーム » Java »【Java】ナップサック問題(knapsack)[動的計画法]

【Java】ナップサック問題(knapsack)[動的計画法]

2015/04/28 Tue [edit]

　最強最速アルゴリズマー養成講座という本の P.177～186 にナップサック問題(knapsack)の解法が載っているのだが(C#,C++,Java 版共に)、品物データの並びを変えると答えが間違って出てくることがあるので、分析してみたらいくつかバグが見つかった。P.180～181 のメモ化再帰でも「return -1;」となっている部分は「return -ps[n - 1];」にしないとバグると思うが、P.184～185 のボトムアップの動的計画法の方は「入れない」処理がされてないので、やはり並びによってはバグる。

　正誤表には載ってないね。検索しても修正版など見つからなかったので、結局 Wikipedia を見ながら書き直したら上手くいった。

●P.184～185 ナップサック問題の動的計画法での解法 O(nW)

int[] ws = {3, 4, 1, 2, 3};  //重さ
int[] ps = {2, 3, 2, 3, 6};  //価値
int maxw = 10;  //重量制限
int[][] dp = new int[ws.length + 1][maxw + 1];
int ret = 0;

for (int i = 0; i < ws.length; i++) {
    for (int j = 0; j <= maxw; j++) {
        if (ws[i] <= j) {
            dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - ws[i]] + ps[i]);
            ret = Math.max(ret, dp[i + 1][j]);
        } else {
            dp[i + 1][j] = dp[i][j];
        }
    }
}
//※答えは dp[ws.length][maxw] でも良い

　C#, C++ 版も同じようなものなので、書き換えれば上手くいくと思う。

　ちなみに問題の内容としては以下の感じになる。

それぞれの重さが ws、価値が ps の品物があります。これらから好きなものを選んで、ナップサックに詰め込みたいと思います。ただしこのナップサックは全部で 10kg までしか入りません。ナップサックに詰め込める品物の価値の和の最大値を求めなさい。

　たぶん元のコードに品物を「入れない」処理

dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);

が抜けているので、それ以前の品物の引き継ぎ状態が消えているのだと思う。配列を出力してみればいくつか抜けているね。あとは不等号やループ変数を ps[j] → ps[i] に修正すれば、上手く動くね。以下のような感じかな。

int[] ws = {3, 4, 1, 2, 3};
int[] ps = {2, 3, 2, 3, 6};
int maxw = 10;
int[][] dp = new int[ws.length + 1][maxw + 1];
int ret = 0;

for (int i = 0; i < ws.length; i++) {
    for (int j = 0; j <= maxw; j++) {
        dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);
        if (j + ws[i] <= maxw) {
            dp[i + 1][j + ws[i]] = Math.max(dp[i + 1][j + ws[i]], dp[i][j] + ps[i]);
            ret = Math.max(ret, dp[i + 1][j + ws[i]]);
        }
    }
}
//※答えは dp[ws.length][maxw] でも良い

　アルゴリズムの解説は、グラフや配列の中身を詳しく書いてあるブログなどがあるのでそちらに譲ろう。私流の解釈としては「それぞれ 1kg, 2kg, 3kg,..., 10kg まで入る器を用意して、次々と品物を『入れるとき』と『入れないとき』(現状のまま)を比べて、価値が大きくなる方だけを残すことを繰り返すと、最後には最大の価値がわかる」と考えればわかりやすい気がする。

　そう考えれば、経過を保存している２次元配列 dp[][] の代わりに、１次元配列を２つ用意して、コピー元とコピー先をひっくり返す手もあるね。コードを見ても直前のインデクスしか参照してないし、２列だけあれば事足りる。データが大量にあるとき、メモリの節約にはなるかもね。ちなみに最大値を保存する ret は、最後の結果の配列の一番右になるので必要ない。また重さ０の列は最後までずっと０なので、ループも１からで良いかも知れない（※Java の場合、配列は０で初期化されるので）。

●経過保存の配列を１次元×２つにして、ちょっぴりメモリ節約版？

int[] src = new int[maxw + 1];    //dp[][] の代わり
int[] dst = new int[maxw + 1];    //dp[][] の代わり
int[] tmp;    //スワップ用

for (int i = 0; i < ws.length; i++) {
    for (int j = 1; j <= maxw; j++) {
        if (j < ws[i]) {
            dst[j] = src[j];
        } else {
            dst[j] = Math.max(src[j], src[j - ws[i]] + ps[i]);
        }
    }
    //参照をスワップ(C言語系ならポインタをスワップ)
    tmp = src;
    src = dst;
    dst = tmp;
}
//最後の結果は src[maxw] になる(スワップしているため)