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

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


 最強最速アルゴリズマー養成講座という本の 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 まで入る器を用意して、次々と品物を『入れるとき』と『入れないとき』(現状のまま)を比べて、価値が大きくなる方だけを残すことを繰り返すと、最後には最大の価値がわかる」と考えればわかりやすい気がする。

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

●経過保存の配列を1次元×2つにして、ちょっぴりメモリ節約版?
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] になる(スワップしているため)


(参考) 01ナップサック問題を動的計画法で解く場合の考え方
(参考) 動的計画法(ナップサック問題)
(参考) ナップサック問題(Wikipedia)

 再帰はデータ量増えると、累乗的に重くなっていくので(最悪オーダー O(2n))、こういう手法はぜひ使いこなしたいものだね。ちなみに「最強最速アルゴリズマー養成講座」という本はそれぞれのアルゴリズム(ナップサックも含む)が図解化されていて非常にわかりやすい。オススメの一冊だ。


(関連記事)
【Java】パスカルの三角形を使って組合せを求める
【Java】ベルマン-フォード法[単一始点最短経路] (Bellman-Ford algorithm, Single Source Shortest Path)
【Java】ダイクストラ法[単一始点最短経路] (Dijkstra's algorithm, Single Source Shortest Path)


■参考になる書籍


スポンサーサイト

category: Java

thread: プログラミング

janre: コンピュータ

tag: アルゴリズム  動的計画法 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/174-3e6879de
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop