java ,ナップサック問題でRuntimeError

Question

Runtime errorになります...
問題はこのサイトです。
AtCoder Beginner Contest 060:D-Simple Knapsack

参考にしました。
Combinatorial - 0-1 Knapsack Problem

失敗するテストケースは
・antigreedy0
・antigreedy1
・antigreedy2
・rand0
・rand1
・rand2
の6つです。それ以外のテストケースはうまくいきました。

なにがいけないのでしょうか？

プログラムは以下の通りです。

import java.util.Scanner;
import java.io.IOException;

class Main{
    public static void main(String[] args)throws IOException{
        int N,W;
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        W = scan.nextInt();
        int[]  v = new int[N+1];  //価値
        int[]  w = new int[N+1]; //重さ
        long[][] dp = new long[N+1][W+1];

        v[0] = 0;
        w[0] = 0;

        //値を取得
        for(int i=1;i<=N;i++){
          w[i] = scan.nextInt();
          v[i] = scan.nextInt();
        }

        //初期化
        for(int i=0;i<=W;i++) dp[0][i] = 0;
        for(int i=0;i<=N;i++) dp[i][0] = 0;

        //ナップサック
        for(int i=1;i<=N;i++){
          for(int j=1;j<=W;j++){
            dp[i][j] = dp[i-1][j];
            if(w[i] > j) continue;
            dp[i][j] = Math.max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]);
          }
        }
        System.out.println(dp[N][W]);

/*
       for(long[] a : dp){
          for(long b : a){
            System.out.print(b +" " );
          }
          System.out.println();
        }
*/
    }
}

Comments

[masaya_ohashi]

RuntimeExceptionのメッセージはもう少し詳しくわからないのでしょうか？

[fuzzball]

long配列の初期値は0らしいので初期化は必要ないですね。

Answer 1

リンク先を見てみると、Wの範囲がかなり広いですね。
試しに最大値である10の9乗要素の配列を作ってみます。

public class Main{
    public static void main(String[] args) {
        int W = (int)Math.pow(10, 9);
        long test[] = new long[W + 1];
    }
}

これを手元でビルド／実行してみた結果、OutOfMemoryErrorが出ました。

---

リンク先をよく読むと、wiの値はw1からw1+3の範囲であることもわかります。
これを踏まえると、dpの要素数は[N+1][4+1]でいいのでは。

Comments

[KSwordOfHaste]

wiが10～13、N=2だったとして、例えば２番目の品物の計算結果で覚えておかなければならない範囲（同じ値が継続しないかもしれない範囲）はi=1のときj=10のみ、i=2で20<=j<=23、i=3で30<=j=<36、...になる気がします。Nが大きくなるにつれ覚えておかなければならない範囲が拡大する傾向にあるのではないでしょうか？
---（上記を一部訂正＆お詫び）---
すみません、中途半端な考えでのコメントをしてしまいました。スルーしてください。