[SWEA] 5215.햄버거 다이어트

 

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Solution {
	
	static int N, L, select;
	static ArrayList<Pair> list, temp;
	static ArrayList answer;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc = 1; tc<=t; tc++) {
			N = sc.nextInt();	// 재료의수
			L = sc.nextInt();	// 제한칼로리
			
			// 재료의 점수와 칼로리를 묶어서 담을 리스트
			list = new ArrayList();
			
			// 뽑은 경우의수를 담을 리스트
			temp = new ArrayList();
			
			// 정답을 모아놓을 리스트
			answer = new ArrayList();
			
			// 초기화
			for(int i=0; i<N; i++) temp.add(new Pair(0, 0));
			
			for(int i=0; i<N; i++) {
				int n = sc.nextInt();
				int m = sc.nextInt();
				list.add(new Pair(n, m));
			}
			
			for(int i=1; i<=N; i++) {
				select = i;
				combi(0, 0);
			}
			
			Collections.sort(answer);
			
			System.out.println("#" + tc + " " + answer.get(answer.size()-1));
		}
	}
	
	public static void combi(int start, int depth) {
		if(depth == select) {
			
//			for(int i=0; i<select; i++) {
//				System.out.print(temp.get(i).score + " " + temp.get(i).kcal + " / ");
//			}
//			System.out.println();
			
			int sum_score = 0;
			int sum_kcal = 0;
			
			for(int i=0; i<select; i++) {
				sum_score += temp.get(i).score;
				sum_kcal += temp.get(i).kcal;
			}
			
			if(sum_kcal <= L) answer.add(sum_score);
			
			return;
		}
		for(int i=start; i<N; i++) {
			temp.set(depth, list.get(i));
			combi(i+1, depth+1);
		}
	}
}

class Pair {
	int score;
	int kcal;
	
	Pair(int score, int kcal) {
		this.score=score;
		this.kcal = kcal;
	}
	
}