03. 최대점수 구하기(DFS)

 

설명

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)

 

 

 

 

입출력

첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다. 두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.

 

첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.

 

 

 

예시

5 20

10 5

25 12

15 8

6 3

7 4

 

41

 

풀이

1. 변수명 무조건 다르게 짓기, 배열 만들때 초기화하기

 

2. 고려할 사항이 많으면 각각 배열을 만들도록 하기

 

3. 최대점수,최대무게, 부분집합 => DFS로 풀기

import java.util.*;
class Main {
	static int n, m;
	static int[] score;
	static int[] time;
	static int max= 0;
	
	public void DFS(int L, int s, int t) {
		if(t>m) {
			return;
		}
		if(L==n) {
//			if(sum>max) {
//				max=sum;
//			}
			max=Math.max(max, s);
		}else {
			DFS(L+1, s+score[L], t+time[L]);
			DFS(L+1, s, t);
		}
	}
	
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		score= new int[n];
		time= new int[n];
		
		for(int i=0; i<n; i++){
			int a = kb.nextInt();
			int b = kb.nextInt();
			score[i]=a;
			time[i]=b;
		}
		T.DFS(0,0,0);
		System.out.println(max);
	}	
}