[swexpert] 5215. 햄버거 다이어트 (java, D3)

부분 집합으로 풀어주었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
		static int t,n,l;
		static int[] scores;
		static int[] calories;
		static int answer;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		t=Integer.parseInt(br.readLine());
		for (int tc = 1; tc <=t; tc++) {
			answer=0;
			st=new StringTokenizer(br.readLine());
			n=Integer.parseInt(st.nextToken());
			l=Integer.parseInt(st.nextToken());
			scores=new int[n];
			calories=new int[n];
			for (int i = 0; i < n; i++) {
				st=new StringTokenizer(br.readLine());
				scores[i]=Integer.parseInt(st.nextToken());
				calories[i]=Integer.parseInt(st.nextToken());
			}
			comb(0,0,0);

			System.out.printf("#%d %d\n",tc,answer);
			
		}
		
	}
	private static void comb(int cnt,int sum,int score) {
		if(cnt==n) {
			if(score>answer)answer=score;
			return;
		}
		if(sum+calories[cnt]<=l) {
			comb(cnt+1,sum+calories[cnt],score+scores[cnt]);
		}
		comb(cnt+1,sum,score);
	
	}

}