ナップザック問題（Java）
はじめに
今回は、アルゴリズムの中で「ナップザック問題」を取り扱っていこうと思う。
このナップザック問題を解くうえで、「動的計画法」を使っていく。
ナップザック問題とは
N種類の品物があり、それぞれの品物には大きさと価値が割り当てられている。
この品物を複数選び、大きさの合計がM以下、価値の合計が最大となる品物の組合せを求めよ、というものである。
この問題を力技で解こうとすると、ある品物を入れるか入れないかで全探索しなければならないため、今回の場合は、2^Nとなる。Nが10程度ならばそれほど問題はないが、数百、数千となれば計算量が膨大になりすぎて終わらなくなってしまう。
動的計画法を用いると、この計算量が格段に少なくできる。
動的計画法とは
まず第一に、最も動的計画法の大事な考え方は、「本当に必要かどうかを考えずに、必要になりそうな小さい問題を先にといてストアしておく」である。
分割統治法の逆の手法とも言える。
分割統治法は、大きな問題を解くときに小さな問題に分解し、それぞれを解くことで最終的に全体を解決する。
動的計画法は、必要・不必要関係なく小さな問題を解き、それらを組み合わせ、最終的に全体を解決する。
分割統治法はトップダウン、動的計画法はボトムアップと考えてよいと思う。
しかし、動的計画法を用いるにあたって、注意すべきなのは、
問題をうまく小さな問題に分割すること。しかし、小さな問題が多すぎてはいけないということ。
この二点を気を付ければ、問題なく使うことができると思う。
解き方
まずは、どのように小さな問題に分割するかが重要であり、今回は、品物を１種類にして問題を解いていくという手法を取る。そして、これに対して、ナップザックの大きさは０からMまでを全て試してみる。それらの解をストアしておく。
次に品物を前回のものに新しく１種類足して、同じことをする。
例えば、あるナップザックの大きさｘがあるとき、新しい種類の品物のサイズ分を空ける。新しい種類の品物のサイズがｙならば、ナップザックの中身をx－yにする。すでに、サイズがx－yを前回の品物１種類だけで埋めたときの結果はストアされているので、あとは、新しいものを足すだけである。もし、このときナップザックの大きさｘを前回の品物だけで埋めた場合よりも価値が高ければ更新する、という処理を繰り返せばよい。
文字で書いてもわかりにくいので、プログラムを書いていく。
ナップザック問題のプログラム
具体的に、ナップザックの大きさなどを定義する。
ナップザックのサイズは16、品は5種類、それぞれの重さは2,3,5,7,9で、価値は2,4,7,11,14とする。
プログラムは以下となる。
public class Knapsack {
int size; //品の大きさ
int N;//品の種類の数
//sizeとvalueの要素の個数が等しいことを確認
throw new IllegalArgumentException
}
//品の種類の数をセットする
this.N = size.length;
//配列sizeの複製を作成。
this.size = (int)size.clone();
}
public void solve(int m) {
//現時点でナップザックに詰め込んだ品物の価値の合計
int total = new int[m+1];
//最後に選んだ品物
int choice = new int[m+1];
Arrays.fill(choice, -1);//全要素を-1に初期化
//品物iを入れたときの価値の合計
int repackTotal;
//ナップザックの大きさを表示
System.out.println("ナップザックの大きさは"+m);
//品物0~iまでを考慮に入れる
for(int i=0;i<N;i++) {
//大きさｊのナップザックにたいして、品物を詰め込んでみる
for(int j=size[i];j<=m;j++) {
//もし、品物iを入れたとすると、価値の合計はいくらになるかを計算して、
//変数repackTotalに入れる
//もし、品物iをいれたほうがいれないより
//価格がおおきくなるのなら、品物iを入れる。
if(repackTotal > total[j]) {
total[j] = repackTotal;
choice[j] = i;
}
}
//配列total,choiceの中身を表示
System.out.println("i = "+i);
System.out.print("total =");
for(int j=0;j<=m;j++) {
System.out.print(total[j]+" ");
}
System.out.println();
System.out.print("choice = ");
for(int j=0;j<=m;j++) {
System.out.print(choice[j]+" ");
}
System.out.println();
}
//どの品物をナップザックに入れたかを表示する
for(int i=m; choice[i] >= 0; i -= size[choice[i]]) {
"を詰め込む");
System.out.println();
}
System.out.print("価値の合計 = "+total[m]);
}
//メインプログラム
public static void main(String args) {
//ナップザック問題を解決するためのオブジェクトを生成する
Knapsack knapsack =
new Knapsack(
new int {2,3,5,7,9},
new int[] {2,4,7,11,14});
System.out.println("入力してください");
Scanner sc = new Scanner(System.in);
int size = sc.nextInt();
knapsack.solve(size);
}
}
プログラムで最も注目してほしいのはsolveメソッドである。total配列には、現時点で入っているものの価値の合計が入っており、choiceは最後に選んだ品物が入る。二重for文では、外側で品物を回し、内側でナップザックの全てのサイズについて価値を図っている。
repackTotal = total[j-size[i]] + value[i];
と書いてあるが、これは先ほど説明した新しい種類の品を入れるときにその分、ナップザックを空けて、品を入れ、価値を足しておく。合計の価値はrepackTotalに入れられる。
そして、その後のif文で、前回の同じナップザックのサイズの時よりも価値が大きければ、更新をして、また新しい品物を加えていくということである。
前回の結果をうまく利用して、最大価値を見つけることができているのが分かる。
実行結果は、次のようになった。
入力してください
16
ナップザックの大きさは16
i = 0
total =0 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16
choice = -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
i = 1
total =0 0 2 4 4 6 8 8 10 12 12 14 16 16 18 20 20
choice = -1 -1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
i = 2
total =0 0 2 4 4 7 8 9 11 12 14 15 16 18 19 21 22
choice = -1 -1 0 1 0 2 1 2 2 1 2 2 1 2 2 2 2
i = 3
total =0 0 2 4 4 7 8 11 11 13 15 15 18 19 22 22 24
choice = -1 -1 0 1 0 2 1 3 2 3 3 2 3 3 3 3 3
i = 4
total =0 0 2 4 4 7 8 11 11 14 15 16 18 19 22 22 25
choice = -1 -1 0 1 0 2 1 3 2 4 3 4 3 3 3 3 4
品物4、価値14を詰め込む
品物3、価値11を詰め込む
価値の合計 = 25
どんどん更新されていき、totalの中で最も数の多いのが最大価値の入れ方となっている。この場合は、i=4のときのtotal=25である。
このナップザックには何が入っているのかを分析するために変数choiceがある、totalが25のときの、choiceは4となっているので、品物４が入っていることが分かる。品物4は価値14であるから、totalから14を引くと、11となる。では、totalが11の時のナップザックには何が入っているのかを調べると、品物3であることが分かる。ちなみに、最大価値11の作り方は他にもあるが、最新のものを出力するようにしたので、品物３，４となっている。
以上がナップザック問題に対して、動的計画法を使った解法である。
参考にしていただけるとありがたいです。
