#概要
01ナップサック問題を分枝限定法の結果が一致しない。
私は今01ナップサック問題を解こうとしています。
しかし、出力結果が私の思い描いていたものとは違っておりどうすればよいのかわかりません。
データとしては
容量が10のナップサックで入れたいものはそれぞれ、
番号0 W = 4 V = 32
番号1 W = 7 V = 35
番号2 W = 6 V = 24
番号3 W = 3 V = 9
です。
#問題点
本来であれば番号0と3が最適解となるはずなのですが必ず番号0が1、それ以外が0となってしまいます。
コードは下記の通りなのですが、どこが間違っているのでしょうか。
再起条件が間違っているような気がするのですが、再起条件はこれで合ってますでしょうか
public class Main {
Java
1 public static int n= 4;//荷物の数は4とする 2 public static int[] W = new int[n];//重さ 3 public static int[] V = new int[n];//価値 4 public static int c = 10;//荷物の容量 5 public static int z = 0; 6 public static int w = 0; 7 public static int v = 0; 8 public static int[] X = new int[n];//暫定解(リュックに何を入れればよいか)
java
1 public static void main(String[] args){ 2 3 W[0] = 4; 4 W[1] = 7; 5 W[2] = 6; 6 W[3] = 3; 7 8 V[0] = 32; 9 V[1] = 35; 10 V[2] = 24; 11 V[3] = 9; 12 13 Napsack(1);//レベル1を渡す...配列でいう0 14 }
java
1 public static void Napsack(int Level){ 2 if(Level > n){//葉の部分...終端 3 w = W[Level - 1] + w;//更新 4 v = V[Level - 1] + v;//更新 5 if((w <= c) && (v > z)){ 6 z = v;///暫定解を更新する 7 X[Level - 1] = 1; 8 9 } 10 }else{//列挙木の内部 11 w = W[Level - 1] + w;//更新 12 v = V[Level - 1] + v;//更新 13 if(w <= c){//容量を超えない 14 if(c == w){//重量と容量が一致 15 z = v; 16 X[Level - 1] = 1;//暫定解とする 17 }else if( v + (c - w) * max(Level - 1) >= z){//上限値が暫定解を上回る 18 X[Level - 1] = 0; 19 Napsack(Level + 1); 20 X[Level - 1] = 1; 21 Napsack(Level + 1); 22 23 } 24 } 25 } 26 27 for(int i = 0; i < n; i++){ 28 System.out.println(X[i]); 29 } 30 31 }
Java
1 public static int max(int l){//ubを決める 2 int max = 0; 3 for(;l < n;l++){//渡された位置より後ろの中でubを定める 4 if(V[l] / W[l] > max){ 5 max = V[l];//最も価値が高いものを選出 6 } 7 } 8 return max; 9 10 }
}
♯01ナップサック問題
容量Cのリュックサック(入れ物)に物を入れていきます。
その時にW(重さ)がC(容量)を超えないように組み合わせて入れていく必要があります。
そうしたときに最もV(価値)が高くなる組み合わせを選ぶというものです。
今回ですと、容量10のナップサックに以下の4つのものを組み合わせて入れていきます。
番号0 W = 4 V = 32
番号1 W = 7 V = 35
番号2 W = 6 V = 24
番号3 W = 3 V = 9
今回の場合ですと最も価値が高くなる、かつCを超えない組み合わせは番号0と番号2の組み合わせになります。
#分枝限定法
上から順番に物を入れるか入れないかの列挙木を作って解いていきます。
そのため、すべての組み合わせを試して行くことになるのですが、その中でこれ以上進めても無駄だろうと判断した場合、それより後の処理をやらずに飛ばしてしまいます。
具体的に言えば上限値が暫定解を下回った場合です。