최대점수 구하기

최대점수 구하기

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

입력 설명

첫 번째 줄에 문제의 개수N(1<=N<=50)과 제한 시간 M(10<=M<=300)이 주어집니다.

두 번째 줄부터 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번째 시간에 풀 수 있는 최대 점수

하지만 이렇게 할 경우

j가 5 -> dy[5] = 10
j가 10 -> dy[5] + 10 = 20

과 같이 문제를 중복으로 푸는 경우가 생길 수 있음.

따라서 중복을 피하기 위해 j가 뒤에서부터 돌아야함.

냅색알고리즘 풀때
1. 문제 종류나 보석의 종류가 무한개 있을 때는 앞에서부터.
2. 개수가 정해져있을때, 종류마다 한개씩 존재, 유한개면 뒤에서부터.