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

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

ただいまの
回答率

90.51%

  • Java

    15779questions

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

動的計画法を用いて部分和問題を解きたいです。

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,214

前提・実現したいこと

このページの問題を解きたいです。
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3886

概要は、いくつかの個数の整数を要素に持つ集合があり、その中から適当な整数を選び出して和をとると、指定した値にできるかどうかを判定するという問題です。集合の要素の個数、集合の要素の値、目標値は全て自分で指定します。

実行例は以下の通りです。

//Sample Input
4                        // テストケース数
25                       // 和を25にしたい
4                        // 集合内にいくつの整数を要素として持つか
10 12 5 7                   // 集合内の4つの整数要素を指定
925                     // 和を925にしたい
10                          // 集合の要素数は10 
45 15 120 500 235 58 6 12 175 70    // 集合内の要素となる10個の整数
120                         // 以下繰り返し
5
25 25 25 25 25
0 
2
13 567

//Sample Output
NO      // その集合では和を25にできない
YES     // 和を925にできる
NO
YES

方針がわかりませんでしたが、いろいろ調べてみると以下のようなサイトを見つけたので、
ここに書いてある方針に倣い、動的計画法を使ってコードを書きました。
http://gushwell.ifdef.jp/etude/SubsetSum.html

発生している問題・エラーメッセージ

コマンドプロンプト上で、上記のSample Input、並びにUDebug(https://www.udebug.com/UVa/12455)にある2つのInput例で試したところ、全く同じ結果が出力されました。
それにも関わらず、UVaでSubmitするとRuntime Errorとなってしまいます。

Runtime Errorについて調べたところ、「配列よりも大きな要素番号にアクセスしたり、ポインタの使用方法が間違っていたりして、セグメントエラーが発生することが主な原因」となるそうですが、もしそうだとしたら、コマンドプロンプト上で実行した時点で、結果が出力される前に何かしらのエラー文が出るのでは?と思いました。(自分はプログラミングができないので、十中八九この推測が違うんだろうとは思いますが)

せめてUVaが何行目でRuntime Errorとなったのか出してくれればいいのですが……
原因がまるで分らないので誰か助けてください……

該当のソースコード

import java.util.StringTokenizer;
import java.io.*;

class Bars {
    public static void main (String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        try {
            String line;
            StringTokenizer token;
            line = br.readLine();
            int testcase = Integer.parseInt(line); // テストケース数

            for(int a=0; a<testcase; a++) {  // テストケース数だけ一連の流れを繰り返す
                line = br.readLine();
                int target = Integer.parseInt(line);   // 目標値 和をこの値にできるかどうか

                if(target==0) System.out.println("YES");  
                         // 目標値が0なら空集合を取れば和を0にできるのでYES
                else {
                    line = br.readLine();
                    int num = Integer.parseInt(line); // 集合の要素数

                    int tmp;
                    int ex = 0;    // 目標値を超えた要素の値が来た時、ex(=exception)をインクリメント
                    int[] bar = new int[num]; // 要素数分の配列
                    line = br.readLine();
                    token = new StringTokenizer(line, " ");

                    for(int i=0; i<num; i++) {
                        tmp = Integer.parseInt(token.nextToken());
                        if(tmp<=target) bar[i-ex] = tmp;  //要素が目標値より小さければ配列に入れる
                        else ex++;   // そうでない場合は配列に入れずにexをインクリメント
                    }            // 2行上でbar[i-ex]としているのは、例外が来ると要素数が減るため

                    num -= ex;       // exの分だけ要素数が入力時よりも減る

// この先は方針の参考にしたサイトに書いてある手順をコードにしました
                    int[] array = new int[target+1];  // 和が0~和がtarget → 大きさがtarget+1の配列
                    array[0] = 0;  // 配列の先頭には0、あとは全て-1を入れて初期化
                    for(int i=1; i<=target; i++) array[i] = -1;
                    boolean judge = false;   // 和がtargetになるとわかったらjudgeをtrueに書き換える

                    // nは参考サイトのnと同じ、jは同サイトにおけるi
                    for(int i=0; i<num; i++) {
                        int n = bar[i];

                        for(int j=target; j>=0; j--) {
                            if(array[j]!=-1) {
                                if(n+j<=target && array[n+j]==-1) array[n+j] = n;
                            }
                        }

       // array[target] (配列の最後)に-1以外が入った瞬間、それは和をtargetにできるということを意味する
                        if(array[target]!=-1) {
                            judge = true;
                            break;
                        }
                    }

                    if(judge) System.out.println("YES");
                    else System.out.println("NO");
                }
            }

        } catch(IOException e) {
                System.out.println("IOException" + e);
                System.exit(1);
        }
    }
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

checkベストアンサー

+2

このコードでは目標数値が0である場合に、それに対応する集合要素の読み込みを行わず、
"Yes"を出力して次のテストケースを読み込むループに入ります。

この結果、その次の行の「集合の要素数」、さらに次の行の「集合の要素」を、
それぞれ次のループで「目標数値」、「集合の要素数」として読み込むことになります。
集合の要素としてスペース区切りとしている文字を要素数として変換しようとするため、
例外が発生してしまいます。

// 例として出ている入力において、最後のテストケースのあとにまだ続きがあったとしたら
0  //これがtargetに変換され、if(target==0)の判定でtrueになり、"Yes"を出力して次のループに移行
2  //次のループでこれがtargetに変換される 0ではないのでelseブロックへ
13 567  //集合の要素数numとしてこの文字列を変換しようとするが、変換できず例外発生


なので、目標数値が0でも、対応する要素数や集合の要素を全部ちゃんと読み込むようにする必要があります。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/05/12 02:09

    なるほど、Sample Inputの目標値が0のときに上手くいっていたのは、その後に何もなかったからですね… 無事Accepted頂きました!!本当にありがとうございます!!!!なんでそんなすぐ気付けるんですか…

    キャンセル

  • 2017/05/12 02:14

    デバッグではコンパイルも通り、テストケースでは問題なく出力される、しかし本番ではRuntimeError。
    つまり、何か特定の条件で例外が発生しているということになります。
    しかもIOExceptionではcatchされてしまうので、例外はRuntimeException系ということになります。
    このコードで起こり得るそれは配列絡みかInteger.parseIntくらいしかないので、そこに絞り込んで考えたまでです。

    キャンセル

  • 2017/05/12 02:46

    なるほど、そういう論理立てになる訳ですね。まだプログラミングの経験と知識に乏しい自分にはなかなか厳しそうです… RuntimeException(実は初めて聞きました)やbinarySearchライブラリなど知らないこともいっぱい教えて下さり、それを自分で調べてみてへ~ってなってるので勉強の助けになってます。いつも本当にありがとうございます!!

    キャンセル

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

  • Java

    15779questions

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