SW Expert Academy_햄버거 다이어트(DP)

//알고리즘.

1. 부분집합으로 풀었던 문제를 DP테이블을 만들어 품.

2. 0/1 knapsack 처럼 정해진 칼로리에 담을 수 있는 칼로리만큼 담고 만족도를 합하여 구함.

 

import java.util.Scanner;

public class 햄버거다이어트_DP {
	static int T,N,L;
	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();
			
			
			int[] arr = new int[N+1];
			int[] cal = new int[N+1];
			
			for (int i = 1; i <= N; i++) {
				arr[i] = sc.nextInt();
				cal[i] = sc.nextInt();
			}
			
			int[][] dp = new int[N+1][L+1];
			
			for (int i = 1; i < dp.length; i++) {
				for (int j = 0; j < dp[i].length; j++) {
					if(cal[i] > j) {
						dp[i][j] = dp[i-1][j];
					}else {
						dp[i][j] = Math.max(arr[i] + dp[i-1][j-cal[i]], dp[i-1][j]);
					}
				}
			}
			
			System.out.printf("#%d %d\n",tc,dp[N][L]);
			
			
			
		}
		
	}

}