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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Java

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

Q&A

解決済

1回答

1439閲覧

java 動的計画法を用いて和の最大値を求めたいです。

RinT_hinabita39

総合スコア28

Java

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

0グッド

0クリップ

投稿2017/05/15 09:33

編集2017/05/15 12:01

###前提・実現したいこと
このページの問題を解きたいです。
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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2017/05/15 17:34

URLの先の問題が違うと思うのですが
guest

回答1

0

ベストアンサー

一通り見てみましたが、確かに例外が発生しそうな箇所は見つけられません。
考えられるのは、GやMに相当する値が非常に大きいものになった場合、2次元配列の確保に必要なメモリが大きくなり、OutOfMemoryErrorになっている可能性が挙げられますが、あまり現実的とは思えません。

とはいえ、無駄にメモリを食っているのは事実なので、そこは見直すべきではないでしょうか。
動的計画法は、目的の値を実現する集合を求めるために使うもので、今回や前回の質問のように値だけ、あるいは成否のみを問うような場合は無駄が多い方法といえます。現に今回のこのコードでは使っている数値は1と-1だけなので、boolean配列で十分といえます。今回はそれが膨大なので、BitSetを使うという手段も考えられます。

また、前回も使っていたStringTokenizerですが、ドキュメントには

StringTokenizerは、互換性を維持する目的で保持されているレガシー・クラスであり、新規コードでは使用が推奨されていません。この機能の使用を考えているなら、Stringのsplitメソッドまたはjava.util.regexパッケージを代わりに使用することをお薦めします。

とあるので、ご検討ください。

投稿2017/05/15 18:06

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

RinT_hinabita39

2017/05/16 08:34

問題のリンクが違うくないですか?と言われて気付いたのですが、まさかの違う問題のページにコードを提出していたのが原因でした… 自分のプログラミング力の低さ故、絶対プログラムに問題があるという前提で考えていたので全く気付きませんでした。変なことで質問してしまってすいません。 授業のDPの説明で1と-1を使っていたのでそうしましたが、確かにbooleanで十分ですね。splitとregexとBitSetについては一度よく調べてみます。ありがとうございました。
RinT_hinabita39

2017/05/16 09:35

split死ぬほど便利ですね…!!今度からこっち使います…
swordone

2017/05/16 10:31

提出間違い、どんまいですw
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問