###前提・実現したいこと
このページの問題を解きたいです。
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2269
概要: いくつかのグループがあり、その各グループにはいくつかの商品(それには当然値段がある)が属しています。
各グループからいずれかの商品を1つずつ買わなければならず、かつ予算内に収めなければなりません。
また、できるだけ購入額が予算の値に近づくようにもさせなければなりません。
そのようにできる場合はその時の合計額を、出来ない場合は"no solution"を出力させます。
//Sample Input 2 //テストケースの数 100 4 //1つ目は予算額、2つ目はグループの数 3 8 6 4 //第1グループ 最初の数はグループの要素数 残りはそのグループに属する商品の額 2 5 10 //第2グループ 4 1 3 3 7 //第3グループ 4 50 14 23 8 //第4グループ 5 3 //2つ目のテストケース 3 6 4 8 2 10 6 4 7 3 1 7 //Sample Output 75 no solution
方針として、table[][]=(グループ数+1)×(予算額+1)の大きさの2次元配列を用意し、各グループの毎にこの商品を買うと残りの予算がどれだけになるというのを調べました。例えば、Sample Inputの2つ目のテストケースの場合、table[0][5]=1とします。これはグループ0(つまり何も買っていない)の段階で、残り予算が5だということを意味します。tableには、グループmの段階で残り予算がnなら、table[m][n]=1を入れます。
次にグループ1を見ると、値段が6、4、8の3つがあるので、もしそれらを買ったとすると残り予算がそれぞれ-1、1、-3となります。
残額が負になってはいけないのでこれは無視して、グループ1の段階で有り得る残額は1のみなので、table[1][1]=1を入れます。
このように、tableにはグループmまで買った段階で、取り得る残額nの全ての組み合わせに対し、table[m][n]=1を入れます。最後にtable[G+1]の行(最後のグループまで買った段階)を見て、残額が0に近いものを取ってきて、その値を予算から引いて、これを出力とします。
###発生している問題・エラーメッセージ
コンパイルは通り、Sample Inputや自分で適当に作った入力でも上手くいっているのですが、UVaに提出するとRuntime Errorになってしまいます。過去にも同様の事があり、その時の経験から、原因は「ある特定の条件の入力」が行われた場合に、何かしらの例外が起きてしまうことだと考えられるのですが、そのような入力パターンが分かりません。それがわかればコードのおかしいところも気付けるかもしれないのですが…
誰かわかる方お願いします。
###該当のソースコード
java
1import java.util.StringTokenizer; 2import java.io.*; 3 4class Wedding { 5 public static void main (String[] args) { 6 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 7 8 try { 9 String line; 10 StringTokenizer token; 11 line = br.readLine(); 12 token = new StringTokenizer(line, " "); 13 int testcase = Integer.parseInt(token.nextToken()); //テストケース数 14 int M, G, K; 15 16 for(int a=0; a<testcase; a++) { //テストケースの数だけループ 17 line = br.readLine(); 18 token = new StringTokenizer(line, " "); 19 M = Integer.parseInt(token.nextToken()); // 予算 20 G = Integer.parseInt(token.nextToken()); // グループ数 21 int[][] table = new int[G+1][M+1]; 22 23 for(int i=0; i<=G; i++) { // table[0][M]=1、それ以外は全部-1を入れる 24 for(int j=0; j<=M; j++) { 25 table[i][j] = -1; 26 } 27 } 28 table[0][M] = 1; 29 30 for(int i=0; i<G; i++) { 31 line = br.readLine(); 32 token = new StringTokenizer(line, " "); 33 K = Integer.parseInt(token.nextToken()); // グループの要素数 34 int[] price = new int[K]; 35 36 for(int b=0; b<K; b++) 37 price[b] = Integer.parseInt(token.nextToken()); // 各要素の値段 38 39 for(int j=M; j>=0; j--) { 40 if(table[i][j]==1) { // 1が入っていれば、それは取り得る残額の値 41 for(int k=0; k<K; k++) { 42 int x = price[k]; 43 if(j-x>=0 && table[i+1][j-x]==-1) // j-k<0だと予算オーバー 44 table[i+1][j-x] = 1; // 元から1が入っている場合は考えない 45 } 46 } 47 } 48 } 49 50 int rest = -1; 51 for(int i=0; i<=M; i++) { 52 if(table[G][i]==1) { 53 rest = i; // tableの最終行を小さいほうから見ていき、1が見つかった時点で終了 54 break; // その時のiは最小の残額(=購入額が最大) 55 } 56 } 57 58 if(rest==-1) System.out.println("no solution"); 59 else System.out.println(M-rest); 60 } 61 62 } catch(IOException e) { 63 System.out.println("IOException" + e); 64 System.exit(1); 65 } 66 } 67} 68
回答1件
あなたの回答
tips
プレビュー