SW Expert Academy_햄버거 다이어트

알고리즘

1. 부분집합을 구해 칼로리의 합을 구함.

2. 칼로리의 합이 제시한 칼로리보다 낮은경우 만족도의 합중 최대값을 저장함.

3. DP테이블을 만들어서 풀이할 수 있음. 추후 업로드 예정

 

import java.util.Scanner;

public class Solution {
	static int T,N,L, arr[][],ans;
	static boolean[] v;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		T= sc.nextInt();
		
		
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			L = sc.nextInt();
			arr = new int[N][2];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 2; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
			v = new boolean[N]; 
			powerSet(0);
			System.out.printf("#%d %d\n",tc,ans);
			ans = 0;
		}
		
	}
	private static void powerSet(int idx) {
		if(idx == N) {
			int csum = 0;
			int psum = 0;
			for (int i = 0; i < N; i++) {
				if(v[i]) {
					psum += arr[i][0];
					csum += arr[i][1];
				}
			}
			if(csum <= L) ans = Math.max(ans, psum);
			
			
			return;
		}
		
		
		v[idx] = true;
		powerSet(idx+1);
		v[idx] = false;
		powerSet(idx+1);
		
		
	}

}