[백준] 12865. 평범한 배낭

https://www.acmicpc.net/problem/12865

 

이차원 배열을 사용한 dp로 풀 수 있는 문제이다. dp[i][j]는 i번째 아이템까지 고려했을 때, 무게 j를 채우는 최대 가치를 의미한다.

 

만약 3번 아이템을 고려할 차례라고 할 때, dp[3][7]은 3번 아이템을 포함하지 않았을 때 무게 7을 채우는 최대 가치(= dp[2][7])와 3번 아이템을 포함했을 때 무게 7을 채우는 최대 가치(= 3번 아이템의 가치 + dp[2][7 - 3번 아이템의 무게]) 중 더 큰 값이 된다.

 

즉, 다음과 같은 점화식이 나온다.

• dp[i][j] = max(dp[i - 1][j], value[i] + dp[i - 1][j - weight[i]])

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] weight = new int[n + 1];
        int[] value = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }

        // dp (dp[i][j]: i번째 아이템까지 고려했을 때, 무게 j를 채우는 최대 가치)
        int[][] dp = new int[n + 1][k + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (j - weight[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], value[i] + dp[i - 1][j - weight[i]]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        System.out.println(dp[n][k]);
    }
}