[알고리즘/SWEA] #5215 햄버거 다이어트

package algorithm_lab.day03.q1;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

public class Hamburger {
	
	static int N, L,max_score;
	static int[] jumsu,cal;
	public static void main(String[] args) throws NumberFormatException, IOException {
		System.setIn(new FileInputStream("./src/algorithm_lab/day03/q1/sample_input.txt"));
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		int test_case=Integer.parseInt(br.readLine());
		
		for(int T=1;T<=test_case;T++) {
			String[] s= br.readLine().split(" ");
			
			N= Integer.parseInt(s[0]);
			L=Integer.parseInt(s[1]);
			jumsu= new int[N];
			cal=new int[N];
			max_score=0;
			
			for(int i=0;i<N;i++) {
				String[] s2=br.readLine().split(" ");
				jumsu[i]=Integer.parseInt(s2[0]);
				cal[i]=Integer.parseInt(s2[1]);
			}
			
			check(0,0,0);
			
			StringBuilder sb=new StringBuilder();
			sb.append("#").append(T).append(" ").append(max_score).append("\n");
			System.out.print(sb.toString());
		}
	}
	
	public static void check(int cnt, int total_score, int total_cal) {
		//기저 조건
		if(total_cal>L) return;
		if(cnt==N) {
			max_score=Math.max(total_score, max_score);
			return;
		}
		
		//해당 재료를 선택 할 때
		check(cnt+1,total_score+jumsu[cnt],total_cal+cal[cnt]);
		// 해당 재료를 선택하지 않을 때
		check(cnt+1,total_score,total_cal);
		
	}
}