最大スコアを取得

最大スコアを取得

今度の情報オリンピックで良い成績を取るために、賢洙は先生からもらったN題をやりたいと思っています.
どの問題にも、解答にかかる点数と解答にかかる時間があります.
制限時間M内では、N個の問題において最大スコアを得る必要がある.
(問題に時間がかかる場合は、問題を解決するとみなされ、各タイプで1つの問題しか解決できません.)

説明の入力

第1行は、問題の数N(1<=N<=50)およびタイムアウトM(10<=M<=300)を与える.
2行目からN行で問題を解くと、点数と問題を解くのにかかる時間が得られます.

出力の説明

最初の行では、有限時間で得られる最大スコアを出力します.

入力

5 20
10 5
25 12
15 8
6 3
7 4

しゅつりょく

41

インプリメンテーションコード

public class 최대점수구하기 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt(); //문제의 개수
        int m = in.nextInt(); //제한 시간
        int[] dy = new int[m+1];

        for(int i=0;i<n;i++){
            int s = in.nextInt();
            int t = in.nextInt();

            for(int j=m;j>=t;j--){
                dy[j] = Math.max(dy[j],dy[j-t]+s);
            }
        }

        System.out.println(dy[m]);
    }
}

他の同じ明示的なアルゴリズムを使用する問題を解決するように.
以下の方法で行います.

for (int i=0;i<n;i++){
            int s = in.nextInt();
            int t = in.nextInt();

            for(int j=0;j<m;j++){
                dy[j] = Math.max(dy[j],dy[j-t]+s);
            }
        }

dy[i]:i 1時間目の授業で解ける最大点数
でもそうすれば
jは5->dy[5]=10
jは10->dy[5]+10=20
重複する問題が発生する可能性があります.
したがって、重複を避けるためには、jは後から回転しなければならない.
シェーディングアルゴリズムを解くとき
1.質問の種類や宝石の種類が無限にある場合は、前から.
2.数量が固定されている場合、各種類は1つ存在し、有限個の後から始まる.