[Baekjoon Online Judge] 12865. 평범한 배낭 (Java)

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

 

설명

---

핵심

용량이 제한된 배낭에 넣을 수 있는 최대 가치를 구하는 유명한 문제인 Knapsack Problem 그 중에서 0/1 Knapsack Problem과 동일한 문제이다.

 

가장 단순한 방법을 생각해보자.

물품의 개수는 최대 100개 이다. 따라서 물품을 넣거나 넣지 않거나 두가지 선택지를 100개 물품에 대해 모두 적용하고 가치를 확인한다면, 2^100가지 상황을 검사해야 한다. 즉, 물품의 개수 N에 대해 시간복잡도가 O(2^N)이다.

 

즉, 시간복잡도를 줄일 방법을 떠올리는 것이 핵심이다. 하지만 이 문제는 워낙 유명하고 떠올리기 쉽지 않기 때문에 그냥 한번 풀어보는 것이 현명한 방법이라고 생각한다.

---

구현

알려진 방법에 따라 시간복잡도를 줄이기 위해서 DP를 이용할 것이다.

1부터 K까지 모든 배낭 용량을 점진적으로 할당하면서 차례대로 검사를 할 것이다. 특이한 점은 대상이 되는 물품을 하나하나 추가한다.

 

Step 1

먼저 첫번째 물품만 고려한다.

허용되는 배낭 용량을 1, 2, ... K 늘려가면서 넣을 수 있는 최대 가치를 검사한다.

첫번째 물품의 무게를 버틸 수 있는 용량이 된다면, 그 배낭에 넣을 수 있는 최대 가치는 첫번째 물품의 가치가 될 것이다.

예시와 같이 첫번째 물품이 (무게 6, 가치 13)이라면 아래와 같이 표현할 수 있다.

	용량 1	용량 2	용량 3	용량 4	용량 5	용량 6	용량 7
물품 1	0	0	0	0	0	13	13

 

Step 2

그 다음 두번째 물품을 포함해서 다시 모든 배낭 용량에 대해 검사를 하는데, 이때 이전 단계의 결과를 활용할 것이다. 두번째 물품은 (무게 4, 가치 8)이다. 

	용량 1	용량 2	용량 3	용량 4	용량 5	용량 6	용량 7
물품 1	0	0	0	0	0	13	13
물품 2	0	0	0	8	8	13	13

 

물품 1의 가치가 더 높기 때문에 용량 6 이상은 여전히 물품 1을 넣는 것이 가치가 크다. 아직 특이한 점은 없다. 다음으로 넘어가보자.

 

Step 3

세번째 물품을 포함한다. 세번째 물품은 (무게 3, 가치 6)이다.

	용량 1	용량 2	용량 3	용량 4	용량 5	용량 6	용량 7
물품 1	0	0	0	0	0	13	13
물품 2	0	0	0	8	8	13	13
물품 3	0	0	6	8	8	13	14

 

여기서 용량 7에 대해 최대 가치가 14(물품 2의 가치 + 물품 3의 가치)가 되었다. 이것은 다음과 같은 점화식에 따라 계산이 된 것이다.

 

DP 테이블:
dp[i][w]: i번째 아이템까지 고려했을 때, 배낭의 최대 무게 w를 채웠을 때의 최대 가치

 

점화식:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - 현재 물품의 무게] + 현재 물품의 가치)
아이템을 선택하지 않는 경우와 선택하는 경우 중 최대값을 선택하는 것이다.

 

dp[i - 1][w - 현재 물품의 무게] + 현재 물품의 가치

이전 단계에서 물품 3의 무게 만큼의 여유 용량이 있는 상황에 대해 물품 3을 넣고 물품 3의 가치를 더한 것이다. 즉, 물품 3이 반드시 포함된 상황에서의 최대 가치를 의미한다.

 

dp[i - 1][w]

물품 2까지만 포함하여 계산한 상황(물품 3이 없는 상황)의 결과를 그대로 적용하는 것이다. dp[2][_]는 물품 2까지만 포함한 상황에 대해서는 최대 가치이기 때문에 물품 3을 포함했을 때의 값보다 크다면 이것을 그대로 사용하는 것이다.

---

Code (Java)

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N + 1][2];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            arr[i][0] = W;
            arr[i][1] = V;
        }

        int[][] d = new int[N + 1][K + 1];
        
        for (int i = 1; i <= N; i++) {
            int w = arr[i][0];
            int v = arr[i][1];
            for (int j = 1; j <= K; j++) {
                if (j >= w) {
                    d[i][j] = Math.max(d[i - 1][j], d[i - 1][j - w] + v);
                } else {
                    d[i][j] = d[i - 1][j];
                }
            }
        }
        System.out.println(d[N][K]);
    }
}