前提・実現したいこと
javaを使ってなってナップサック問題を動的計画法を使用して解きたいです。
データはcsvファイルから取りこむ形で、重さw[],価値v[]に格納して計算しようとしています。
発生している問題・エラーメッセージ
まずなぜこのような結果が表示されているのかわかりません。
また、実行時間はほかのメソッドで違う手法で計算してその計算時間も出しているのですが、それに依存して同じ時間が表示されている状況です。
動的計画法で解いた場合 [I@1b6d3586番目の組み合わせが最適解 実行時間... time: 41241.268756 ms.
該当のソースコード
メソッドと出力のところが違うと考えています。
また、 sol = dp(b); // 動的計画法のメソッドの呼び出しと最適値の受け取り
の部分の**(b)の部分もおかしいです**。。
java
1import java.io.*; 2public class Knupsuq5 { 3 static final int N = 20; // 製品数 4 static final int W = 15;// 重量上限 5 static int[] w = new int[N]; // 製品iの重量 6 static int[] v = new int[N]; // 製品iの価値 7 static int[] b = new int[N]; // 入れるか入れないかの0-1変数 8 static int i = 0; 9 static int[][] dp=new int[w.length+1][W+1]; 10static int dp(int []bootlearn){ 11 int ret = 0; 12 for (int i = 0; i < w.length; i++) { 13 for (int j = 0; j <= W; j++) { 14 if (w[i] <= j) { 15 dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]); 16 ret = Math.max(ret, dp[i + 1][j]); 17 } else { 18 dp[i + 1][j] = dp[i][j]; 19 } 20 } 21 for(int j=0;j<N;j++) { 22 bootlearn[j]=dp[i][j]; 23 System.out.println(); 24 return dp[0][0]; 25 } 26 } 27 return ret; 28 } 29public static void main(String[] args) { 30 // TODO 自動生成されたメソッド・スタブ 31 String str; 32 i = 0; 33 int sol; 34 String[] s = {"詰めない", "詰める"}; // 解表示用文字列 35 // データの読み込み 36 try{ 37 File data = new File("C:\data.csv"); 38 BufferedReader br = new BufferedReader(new FileReader(data)); 39 while((str = br.readLine()) != null){ 40 String[] st = str.split(",", 0); 41 w[i] = Integer.parseInt(st[0]); 42 v[i] = Integer.parseInt(st[1]); 43 System.out.printf("%2d %2d %2d\n",i, w[i], v[i]); 44 i++; 45 } 46 }catch(FileNotFoundException e){ 47 System.out.println("ファイルが見つかりませんでした."); 48 }catch(IOException e){ 49 System.out.println("入出力でエラーが発生しました"); 50 } 51 52// 動的計画法で解く場合 53 System.out.println("動的計画法で解いた場合"); 54 t0 = System.nanoTime(); 55 sol = dp(b); // 動的計画法のメソッドの呼び出しと最適値の受け取り 56 System.out.println(dp[0] + "番目の組み合わせが最適解"); 57 System.out.printf("実行時間...%ntime: %f ms.%n", time/1000000.0); 58 59 } 60 61 62 }
最後に・・・
javaを使ってのプログラムプログラムは約1年ぶりのため忘れていることも多いです。なので訳のわからないコードになっていると思われますが
回答をよろしくお願いします。
補足情報(FW/ツールのバージョンなど)
開発環境はequlipseを使っています。
回答1件
あなたの回答
tips
プレビュー