Java 動的計画法を使ってナップサック問題を解く

Question

前提・実現したいこと

javaを使ってなってナップサック問題を動的計画法を使用して解きたいです。
データはcsvファイルから取りこむ形で、重さw[],価値v[]に格納して計算しようとしています。

発生している問題・エラーメッセージ

まずなぜこのような結果が表示されているのかわかりません。
また、実行時間はほかのメソッドで違う手法で計算してその計算時間も出しているのですが、それに依存して同じ時間が表示されている状況です。

動的計画法で解いた場合
[I@1b6d3586番目の組み合わせが最適解
実行時間...
time: 41241.268756 ms.

該当のソースコード

メソッドと出力のところが違うと考えています。
また、 sol = dp(b); // 動的計画法のメソッドの呼び出しと最適値の受け取り
の部分の**(b)の部分もおかしいです**。。

import java.io.*;
public class Knupsuq5 {
	static final int N = 20;	// 製品数
	static final int W = 15;// 重量上限
	static int[] w = new int[N]; // 製品iの重量
	static int[] v = new int[N]; // 製品iの価値
	static int[] b = new int[N]; // 入れるか入れないかの0-1変数
	static int i = 0;
    static int[][] dp=new int[w.length+1][W+1];
static int dp(int []bootlearn){
		int ret = 0;
		for (int i = 0; i < w.length; i++) {
		    for (int j = 0; j <= W; j++) {
		        if (w[i] <= j) {
		            dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);
		            ret = Math.max(ret, dp[i + 1][j]);
		        } else {
		            dp[i + 1][j] = dp[i][j];
		        }
		    }
		    for(int j=0;j<N;j++) {
		    	bootlearn[j]=dp[i][j];
		    	System.out.println();
		    	return dp[0][0];
		    }
		    }
		return ret;
		}
public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		String str;
		i = 0;
		int sol;
		String[] s = {"詰めない", "詰める"}; // 解表示用文字列
		// データの読み込み
		try{
			File data = new File("C:\data.csv");
			BufferedReader br = new BufferedReader(new FileReader(data));
			while((str = br.readLine()) != null){
				String[] st = str.split(",", 0);
				w[i] = Integer.parseInt(st[0]);
				v[i] = Integer.parseInt(st[1]);
				System.out.printf("%2d %2d %2d\n",i, w[i], v[i]);
				i++;
			}
		}catch(FileNotFoundException e){
			System.out.println("ファイルが見つかりませんでした．");
		}catch(IOException e){
			System.out.println("入出力でエラーが発生しました");
		}

// 動的計画法で解く場合
		System.out.println("動的計画法で解いた場合");
		t0 = System.nanoTime();
	    sol = dp(b); // 動的計画法のメソッドの呼び出しと最適値の受け取り
		System.out.println(dp[0] + "番目の組み合わせが最適解");
		 System.out.printf("実行時間...%ntime: %f ms.%n", time/1000000.0);
		
	}
	

	}

最後に・・・

javaを使ってのプログラムプログラムは約1年ぶりのため忘れていることも多いです。なので訳のわからないコードになっていると思われますが
回答をよろしくお願いします。

補足情報（FW/ツールのバージョンなど）

開発環境はequlipseを使っています。

Comments

[shiron46]

貼られたコードが古かったりしないでしょうか？コンパイルエラーはありますし、dpメソッドはほとんどループせずに抜けているので40秒もかかるコードには見えませんが…

[keyakizaka17]

コードは古いはずはないんですけどもなぜこんなに時間がかかるのかもわかりません。これを実装する前に別の解法のものでやりましたが0.4秒程度でできたのでやはりこのメソッド自体が悪い可能性がありますよね？

[shiron46]

そうですか…。では本コードについて、怪しそうな箇所を回答に追記しておきます。

Answer 1

現時点で分かっている箇所について回答しておきます。

まずなぜこのような結果が表示されているのかわかりません。

原因は↓です。

    static int[][] dp=new int[w.length+1][W+1];
    // （中略）
        System.out.println(dp[0] + "番目の組み合わせが最適解");

dpは2次元配列ですが、1次元分しかインデックスを指定していないためです。

---

以下は見直し方が良さそうな箇所です。

• dpメソッド内のループ条件

特に下記のコードは問題があります。
-- ループに入ると無条件でreturnしてしまいます。
-- 配列dp の2次元目は大きさW(15)ですが、N(20)までループさせようとしています。

            for(int j=0;j<N;j++) {
                bootlearn[j]=dp[i][j];
                System.out.println();
                return dp[0][0];
            }

　

参考URL

pieceofnostalgy.blogspot.com/2013/12/01.html

Comments

[keyakizaka17]

ご丁寧な回答を
ありがとうございます。
そのやり方で
少し考えてみます！

[keyakizaka17]

なるほど！
最初の設定と処理ががずれてるとことですね
もう一回考察してみます。
わかりやすい回答をありがとうございます！

もしよければshiron46さんであれば
どういう風にこの問題を解くか教えていただけませんでしょうか？

[shiron46]

すみません、コードを読み間違えていました。ナップサックの残容量は考慮されていますね。
回答は修正しておきます。

問題を解く方針は同じになると思いますが、重さと価値をもつ製品クラスは作ります。
回答に追記した参考URLに詳しい解説およびJavaのサンプルコードが載っていますので、ぜひ参考にしてみてください。

[keyakizaka17]

ありがとうございます
なんとか行けそうな気がします！
ご丁寧に回答をありがとうございました！
あと３日他の方のコメントがなければベストアンサーにさせていただきます！