Runtime errorになります...
問題はこのサイトです。
AtCoder Beginner Contest 060:D-Simple Knapsack
参考にしました。
Combinatorial - 0-1 Knapsack Problem
失敗するテストケースは
・antigreedy0
・antigreedy1
・antigreedy2
・rand0
・rand1
・rand2
の6つです。それ以外のテストケースはうまくいきました。
なにがいけないのでしょうか?
プログラムは以下の通りです。
lang
1import java.util.Scanner; 2import java.io.IOException; 3 4class Main{ 5 public static void main(String[] args)throws IOException{ 6 int N,W; 7 Scanner scan = new Scanner(System.in); 8 N = scan.nextInt(); 9 W = scan.nextInt(); 10 int[] v = new int[N+1]; //価値 11 int[] w = new int[N+1]; //重さ 12 long[][] dp = new long[N+1][W+1]; 13 14 v[0] = 0; 15 w[0] = 0; 16 17 //値を取得 18 for(int i=1;i<=N;i++){ 19 w[i] = scan.nextInt(); 20 v[i] = scan.nextInt(); 21 } 22 23 //初期化 24 for(int i=0;i<=W;i++) dp[0][i] = 0; 25 for(int i=0;i<=N;i++) dp[i][0] = 0; 26 27 //ナップサック 28 for(int i=1;i<=N;i++){ 29 for(int j=1;j<=W;j++){ 30 dp[i][j] = dp[i-1][j]; 31 if(w[i] > j) continue; 32 dp[i][j] = Math.max(v[i]+dp[i-1][j-w[i]],dp[i-1][j]); 33 } 34 } 35 System.out.println(dp[N][W]); 36 37/* 38 for(long[] a : dp){ 39 for(long b : a){ 40 System.out.print(b +" " ); 41 } 42 System.out.println(); 43 } 44*/ 45 } 46}
回答1件
あなたの回答
tips
プレビュー