[Java] SWEA - 햄버거 다이어트

DP문제입니다.

(knapsack problem) 배낭채우기 문제로 2차원 배열을 사용합니다.
음식을 차례대로 기록합니다.

1번째 음식을 맛/칼로리로 기록합니다.
2번째 음식에서 [이전에 기록된 맛]과 [기록된 칼로리 - 현재 칼로리 위치의 맛 + 현재 맛]을
비교해서 큰 값으로 저장합니다.
이를 반복해서 가장 좋은 방법을 도출해냅니다.

점화식

dp[i][j] = Math.max(arr[i] + dp[i-1][j-cal[i]], dp[i-1][j]);

 

import java.util.*;
import java.io.*;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {               
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
         
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int n;
            int m;
            n = sc.nextInt();
            m = sc.nextInt();
             
            int[] arr = new int[n+1]; 
            int[] cal = new int[n+1];
            int[][] dp = new int[n+1][m+1];
                 
            for (int i=1; i<=n; ++i){
                arr[i] = sc.nextInt();   
                cal[i] = sc.nextInt();
            }
             
            for(int i=1; i<dp.length; ++i){
                for(int j=1; 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.println("#" + test_case + " " + dp[n][m]);
        }
    }
}