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

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

ただいまの
回答率

90.34%

  • Java

    14419questions

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

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

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 243

keyakizaka17

score 2

 前提・実現したいこと

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を使っています。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • shiron46

    2018/07/04 20:54

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

    キャンセル

  • keyakizaka17

    2018/07/04 22:31

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

    キャンセル

  • shiron46

    2018/07/04 23:42 編集

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

    キャンセル

回答 1

checkベストアンサー

+3

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

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

原因は↓です。

    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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/07/04 22:33 編集

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

    キャンセル

  • 2018/07/05 12:57

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

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

    キャンセル

  • 2018/07/05 19:20

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

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

    キャンセル

  • 2018/07/06 12:26

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

    キャンセル

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

  • ただいまの回答率 90.34%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • Java

    14419questions

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