###前提・実現したいこと
javaで動的計画法を使ってナップサック問題を解くプログラムを作りたいです。
行列の行が荷物、列がナップサックの容量としています。
・それぞれの荷物数とナップサックの容量の組み合わせについて、最適解(価値の合計の値)を求めて、それを配列 G[][] に格納する
・booleanの配列 S[][] を使って、最適解 G[k][i] を得るためにk番目の荷物を選択した場合にS[k][i]をtrue、それ以外の場合はfalseとなる S[][] の作成
ここまでは上手くいっています。この後、S[][]を使って、荷物kを取ったか取っていないかをbooleanで表したSS[]を以下の方針で作りたいです。
・S[k][i]がtrueなら、G[k][i]から荷物kの重さを引いて、その引いた後の値とG[k][i]が等しくなるまでi--;する
・i--;がされなくなったら、S[k][i]の値にかかわらず、S[k][i]がtrueになるまでk--;する
・これらをG[k][i]からどんどん値が引かれ、0になるまで繰り返す(コードではtotalとおいています)
###発生している問題・エラーメッセージ
引数に荷物の数と、ナップサックの容量を与えるのですが、上手くいく組み合わせと上手くいかない組み合わせがあります。上手くいかない場合は、break;って書いたのになぜかbreakせず、無限ループしてしまいます。
###該当のソースコード
java
1 2public class DPKnapsack2 { 3 static int [] v = {0, 250, 300, 160, 420, 450, 510, 557, 490, 721, 600}; 4 static int [] w = {0, 1, 2, 3, 4, 6, 5, 8, 7, 10, 9}; 5 6 public static boolean[] knapsack (int [] v, int [] w, int n, int C) { 7 int k, i, v1; 8 int [][] G = new int[n+1][C+1]; 9 boolean [][] S = new boolean [n+1][C+1]; 10 boolean [] SS = new boolean [n+1]; 11 12 for(int a=0; a<=n; a++) { 13 for(int b=0; b<=C; b++) { 14 G[a][b] = 0; 15 S[a][b] = false; 16 } 17 } 18 19 for(int a=1; a<=n; a++) { 20 for(int b=1; b<=C; b++) { 21 if(b<w[a]) { 22 G[a][b] = G[a-1][b]; 23 } else { 24 v1 = G[a-1][b-w[a]] + v[a];; 25 if(G[a-1][b] < v1) { 26 G[a][b] = v1; 27 S[a][b] = true; 28 } else { 29 G[a][b] = G[a-1][b]; 30 } 31 } 32 } 33 } 34 35 for(int a=0; a<=n; a++) 36 SS[a] = false; 37 38 k = n; i = C; 39 int total = G[k][i]; 40 41 //ここより下が問題の箇所です 42 43 while (true) { 44 if (S[k][i] == true) { 45 SS[k] = true; 46 total = total - v[k]; 47 if (total == 0) break; 48 while (total != G[k][i]) { 49 if (i>=1) i--; 50 else { 51 i = C; 52 break; 53 } 54 System.out.println(k+" "+i); 55 } 56 } 57 while (S[k][i] == false) {k--; System.out.println(k+" "+i);} 58 } 59 60 return SS; 61 } 62 63 //これ以降は問題ないです 64 65 public static void main(String [] args) { 66 if (args.length == 2) { 67 int k = Integer.parseInt(args[0]); 68 int i = Integer.parseInt(args[1]); 69 boolean [] S = knapsack(v, w, k, i); 70 int total = 0; 71 for (k=1; k<S.length; k++) 72 if (S[k]) { 73 total = total + v[k]; 74 System.out.println("重さ "+w[k]+" 価値 "+v[k]); 75 } 76 System.out.println("合計価値 "+total); 77 } else 78 System.out.println("1~2個の引数を与えてください"); 79 } 80}
###注釈
i--,k--付近にある System.out.println(k+" "+i); は、自分が今荷物数が何で、容量が何を見ているかのデバッグ用です。
###実行例
上手くいく例
java DPKnapsack2 10 10
9 10
8 10
7 10
6 10
6 9
6 8
6 7
6 6
6 5
5 5
4 5
4 4
4 3
4 2
4 1
3 1
2 1
1 1
重さ 1 価値 250
重さ 4 価値 420
重さ 5 価値 510
合計価値 1180
ダメな例
C:\Users\RinRin\Desktop\prog>java DPKnapsack2 10 15
9 15
8 15
7 15
6 15
6 14
6 13
6 12
6 11
6 10
6 9
6 8
6 7
6 6
6 5
6 4
6 3
6 2
6 1
6 0
6 14
6 13
6 12
6 11
6 10
6 9
6 8 (以下ループ)
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。