최대점수 구하기(냅색 알고리즘)

 

 

dy[j]는 나에게 j분이 주어졌을 때 얻을 수 있는 최대 점수이다.

d[16]은 16분이 주어졌을 때 얻을 수 있는 최대 점수

앞의 문제 처럼 앞에서 부터 탐색하면 해당 문제를 2번 풀 수 있게 되어버린다!

그렇기 때문에 뒤에서부터 탐색하여 1번씩만 풀 수 있게 한다.

 

갯수가 무한정이다 - 앞에서부터

갯수가 무한정이 아니다 - 뒤에서부터

i = 0일 때

j = 20 ~ 5까지 돔 - 제한 시간이 5분이라서 20 ~ 5분 문제 풀 수 있음

dy[20] = Math.max(dy[20], dy[20-5]+10) = 10 - 5분 걸리는 10점 문제 하나 풀음

...

dy[5] = Math.max(dy[5], dy[5-5]+10) = 10 - 5분 걸리는 10점 문제 하나 풀음

 

i = 1일 때

j = 20 ~ 12까지 돔 - 제한 시간이 12분이라서 20 ~ 12분 문제 풀 수 있음

dy[20] = Math.max(dy[20], dy[20-12]+25 = 35 - 10점 문제 하나 + 12분 걸리는 25점 문제 하나 풀음

...

dy[16] = Math.max(dy[16], dy[16-12]+25 = 25 - 12분 걸리는 25점 문제 하나 풀음

...

dy[12] = Math.max(dy[12], dy[12-12]+25 = 25 - 12분 걸리는 25점 문제 하나 풀음

 

i = 2일 때

j = 20 ~ 8까지 돔 - 제한 시간이 8분이라서 20 ~ 8분 문제 풀 수 있음

dy[20] = Math.max(dy[20], dy[20-8]+15) = 40 - 25점 문제 하나 + 8분 걸리는 15점 문제 하나 풀음

 

i = 3일 때

j = 20 ~ 3까지 돔 - 제한 시간이 3분이라서 20 ~ 3분 문제 풀 수 있음

dy[20] = Math.max(dy[20], dy[20-3]+6) = 41 - 10점 문제 하나 + 25점 문제 하나 + 6점 문제 하나 풀음

 

i = 4일 때

j = 20 ~ 4까지 돔- 제한 시간이 4분이라서 20 ~ 4분 문제 풀 수 있음

dy[20] = Math.max(dy[20], dy[20-4]+7) = 38 - 25점 문제 하나 + 6점 문제 하나 + 7점 문제 하나 풀음

 

dy[20] = 41

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int m=kb.nextInt();
        int[] dy=new int[m+1];
        for(int i = 0; i < n; i++) {
            int ps=kb.nextInt();
            int pt=kb.nextInt();
            for(int j=m; j>=pt; j--){
                dy[j]=Math.max(dy[j], dy[j-pt]+ps);
            }
        }
        System.out.print(dy[m]);
    }
}