Finding the Maximum Score (DFS)

Problem

In order to get good grades in this information olympiad, Hyun-soo is going to solve the N problems given by the teacher. Each question is given a score for solving it and the time it takes to solve it. We need to get the maximum score out of N problems within the time limit M. (The problem is considered to be solved if it takes time. Only one can be solved per type.)

input

• The first line gives the number of problems N (1<=N<=20) and a time limit M (10<=M<=300)
• From the second line to N lines, the score for solving the problem and the time taken to solve are given

5 20
10 5
25 12
15 8
63 74

output

The first line prints the maximum score that can be obtained within the time limit.

41

Solution

function solution(m, ps, pt) {
	let answer = Number.MIN_SAFE_INTEGER,
		n = ps.length;
	function DFS(L, score, time) {
		if (time > m) return;
		if (L >= n) {
			answer = Math.max(answer, score);
		} else {
			DFS(L + 1, score + ps[L], time + pt[L]);
			DFS(L + 1, score, time);
		}
	}
	DFS(0, 0, 0);

	return answer;
}