삼성 SW 5223번 햄버거 다이어트

풀이방법

각각의 재료마다 점수와 칼로리가 다른데 제한칼로리를 채우기 위해
부분합 알고리즘을 사용했다.

부분합 함수에서 재료를 추가하는경우 , 추가 안하는 경우 따로따로 재귀를 했다
그리고 제한 칼로리보다 작은 경우는 리스트에 추가하고 점수가 가장 높은것을 뽑았다.

package com.day8;

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

public class SW5223_Hambuger {
	public static int [][]arr;
	public static boolean [] visited;
	public static int num;
	public static int limit;
	public static ArrayList<Integer> list;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int a = 1 ; a <= tc ; a++) {
			num = sc.nextInt();   //재료의 갯수
			limit = sc.nextInt(); //제한 칼로리
			
			arr= new int[num][2];
			visited = new boolean[num];
			list = new ArrayList<>();
			for(int i = 0 ; i < num ; i++) {
				arr[i][0]= sc.nextInt();   //각각의 점수
				arr[i][1] = sc.nextInt();  //각각의 칼로리
			}
			
			//부분합 함수 호출
			subset(0,0,0);
			
			//리스트에서 최대값 뽑아서 출력
			int max = Collections.max(list);
			System.out.printf("#%d ",a);
			System.out.println(max);
		}
	}
	
	//재료를 뽑을지 말지 정하는 서브셋 함수
	private static void subset(int cnt, int score, int cal) {
		//재료의 갯수만큼 서브셋을 뽑고
		if(cnt == num ) {
			//제한 칼로리보다 적은 경우에만
			if(cal <= limit)
				//해당 점수를 리스트에 추가
				list.add(score);
			return;
		}
		
		//현재 재료를 추가하는 경우
		visited[cnt] = true;
		//현재 cnt에서의 점수와 칼로리를 더하면서 재귀
		subset(cnt+1, score + arr[cnt][0] , cal + arr[cnt][1]);
		
		//현재 재료를 추가 안하는 경우
		visited[cnt] = false;
		subset(cnt+1, score, cal);
		
	}
}