##解決したいこと
javaを使って全探索で問題を解くアルゴリズムを作っています。動的計画法との計算時間の比較を行いたいため非効率であることは承知の上で行っています。しかし、要素数が31個以上で全探索を解くとOutof Memory Errerが起き計算ができなくなります。
配列の上限解放について、解決できるよい方法があれば教えていただけるとありがたいです。
java
1static final int N = 30; // 製品数 2 static final int W = 20;// 重量上限 3 static int[] w = new int[N]; // 製品iの重量 4 static int[] v = new int[N]; // 製品iの価値 5 static int[] b = new int[N]; // 入れるか入れないかの0-1変数 6 static int i = 0; 7static int allCombi(int[] optimal){ 8 System.out.println("全組み合わせとその時の価値合計および重量合計"); 9// int i = 0; // 組み合わせ番号 10 for(int i = 0; i < (int)Math.pow(2.0,N); i++){ 11 val[i] = 0; 12 wgt[i] = 0; 13 for(int k = 0; k < N; k++){ 14 b[N - k - 1] = (i >>> k & 1) == 1 ? 1 : 0; 15 // 目的関数 16 val[i] += b[k]*v[k]; // val[i] = b[0]*v[0]+b[1]*v[1]+b[2]*v[2]+b[3]*v[3]+b[4]*v[4]+b[5]*v[5]; 17 // 重量合計 18 wgt[i] += b[k]*w[k]; // wgt[i] = b[0]*w[0]+b[1]*w[1]+b[2]*w[2]+b[3]*w[3]+b[4]*w[4]+b[5]*w[5]; 19 } 20 System.out.printf("%2d %d %d %d %d %d %d %2d %2d\n", i + 1, b[0], b[1], b[2], b[3], b[4], b[5], val[i], wgt[i]); 21 if(max[0] < val[i] && wgt[i] <=W){ 22 max[0] = val[i]; 23 max[1] = wgt[i]; 24 max[2] = i + 1; 25 for(int j = 0; j < N; j++){ 26 optimal[j] = b[j]; 27 } 28 } 29 } 30 System.out.println(); 31 return max[0]; 32 } 33String str; 34 i = 0; 35 int sol; 36 String[] s = {"詰めない", "詰める"}; // 解表示用文字列 37 // データの読み込み 38 try{ 39 File data = new File("C:\Users\fit-user\Desktop\data1.csv"); 40 BufferedReader br = new BufferedReader(new FileReader(data)); 41 while((str = br.readLine()) != null){ 42 String[] st = str.split(",", 0); 43 w[i] = Integer.parseInt(st[0]); 44 v[i] = Integer.parseInt(st[1]); 45 System.out.printf("%2d %2d %2d\n",i, w[i], v[i]); 46 i++; 47 } 48 }catch(FileNotFoundException e){ 49 System.out.println("ファイルが見つかりませんでした."); 50 }catch(IOException e){ 51 System.out.println("入出力でエラーが発生しました"); 52 } 53 // 全組み合わせ列挙で解く場合 54 System.out.println("全組み合わせ列挙で解いた場合"); 55 t0 = System.nanoTime(); 56 sol = allCombi(optimal); // 全組み合わせ列挙メソッドの呼び出しと最適値の受け取り 57 System.out.println(max[2] + "番目の組み合わせが最適解"); 58 // 最適解の表示 59 for(int i = 0; i < N; i++){ 60 System.out.println("製品" + i + ":" + s[optimal[i]]); 61 } 62 System.out.println("最適値:" + sol); 63 System.out.println("重 量:" + max[1]); 64 time = System.nanoTime() - t0; 65 System.out.printf("実行時間...%ntime: %f ms.%n", time/1000000.0); 66
開発環境
開発環境としてはequlipseを使っています。

回答5件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/07/12 03:08