質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

2回答

5829閲覧

java 動的計画法を用いたナップサック問題を解くプログラム

RinT_hinabita39

総合スコア28

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2016/07/31 11:42

編集2016/07/31 11:59

###前提・実現したいこと
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 (以下ループ)

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

変数名は1文字ではなくわかりやすいものを付けた方が良いでしょう(自分しかみないなら構いませんが)。

細部までみていませんので原因までは突き止めてませんが、途中でtotalがマイナスになっています。
そのtotalと合うG[k][i]はたぶんありませんので無限ループになっています。

java

1total = total - v[k]; 2if (total == 0) break;

を、

java

1total = total - v[k]; 2System.out.println(total+" "+v[k]); 3if (total == 0) break; 4if (total < 0) break;

としてみれば状態は追いやすいかもしれません。

投稿2016/07/31 13:08

flied_onion

総合スコア2604

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

total = total - v[k];の結果でtotalが負の値になった場合、ループがbreakすることがなくなり、無限ループになっているのだと思われます。

- if (total == 0) break; + if (total <= 0) break;

と変えてみるとうまくいくと思います。

投稿2016/07/31 12:39

編集2016/07/31 12:41
raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

RinT_hinabita39

2016/07/31 18:27

totalを出力させてみたら確かに負の値になってましたね… 僕の予定でも、問題の意図的にも絶対負にはならないはずなのですが… どこか僕の実装の方針が違っているということでしょうか。 ベストアンサーは早かったraccyさんとさせて頂きました。お二方ともありがとうございました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問