최대점수 구하기

현수는 선생님이 주신 N개의 문제를 풀려고 합니다.

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

제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.

(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

 

입력                 출력

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

 

전, 전전문제와 비슷한 부분집합 합 구하기 문제, 조건에 시간제한도 더해주면서 bfs를 한다

 

import java.util.*;


public class Main{
    static int[] times, score;

    static int max = Integer.MIN_VALUE, timeLimit = 0;

    public void dfs(int v, int limit, int sum){
        if (limit > timeLimit) return;

        if( v == times.length){
            max = Math.max(max, sum);
        }

        else {
            dfs(v+1, limit + times[v], sum + score[v]);
            dfs(v+1, limit, sum);
        }
    }

    public static void main(String args[]) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        timeLimit = in.nextInt();
        score = new int[n];
        times = new int[n];
        for (int i =0; i< n; i++) {
            score[i] = in.nextInt();
            times[i] = in.nextInt();
        }

        T.dfs(0, 0, 0);

        System.out.print(max);
    }
}