[Java] 백준 BOJ / 12865번: 평범한 배낭

개미개미개·2025년 1월 8일

DP 알고리즘

Algorithm

목록 보기

5/63

평범한 배낭

문제

알고리즘 설명

이 문제는 배낭 문제(knap sack)으로 많이 알려진 문제이다.
대학교 2학년 2학기 때 알고리즘 수업때 다이내믹 프로그래밍 수업을 들었을 때 배웠던 문제였는데 오랜만에 푸니 잘 풀리지 않았다.

배낭문제는 크게 두가지 문제로 분류된다.

1. 짐을 쪼갤 수 있는 경우 (Fraction Knapsack Problem)
2. 짐을 쪼갤 수 없는 경우 (0/1 Knapsack Problem)

이렇게 두가지로 분류 된다.

짐을 쪼갤 수 있는 문제(Fraction Knapsack Problem)은 이번 문제와는 다르게
Greedy 알고리즘을 적용해서 풀고 이번 문제 같은 짐을 쪼갤 수 없는 경우(0/1 Knapsack Problem)은 Dynamic Programming을 사용해서 푼다.

이번 문제에서 DP 테이블을 채우는 방법에 대해서 알아보자.

예제 입력에서 사용된 값을 사용하여 DP 테이블을 채우면
무게 배열 W와 가치 배열 V가 있다고 할 때 W와 V의 관계는 아래 수식과 같다.

(W_i, V_i) = (6, 13), (4, 8), (3, 6), (5, 12)

1. 수용가능한 물건이 없을 경우

dp	0	1	2	3	4	5	6	7
1	0	0	0
2	0	0	0
3	0	0	0
4	0	0	0

위 표와 같이 dp[2] 까지는 수용가능한 물건이 없기 때문에 모두 0으로 채워질 것이다.

2. 수용 가능한 물건이 하나일 경우

1) dp[3]

dp[3] 을 채울 차례인데 무게 3을 수용할 수 있는 경우는 i = 3 일 때부터 채울 수 있기 때문에 아래의 표와 같이 채워진다.

dp	0	1	2	3	4	5	6	7
1	0	0	0	0
2	0	0	0	0
3	0	0	0	6
4	0	0	0	6

i 가 4일 경우를 생각해보면 dp[3]일 경우 현재 수용할 수 있는 무게가 3이라는 말이기 때문에 i=4일경우 무게 5를 수용할 수 없기 때문에 가장 최대의 값인 6을 채우는 것이다.

2) dp[4]

i = 2 일때 무게는 8이 가능하기 때문에 8을 채워주고 그 이후 값 또한 현재까지의 최대인 8을 채워준다.

dp	3	4
1	0	0
2	0	8
3	6	8
4	6	8

3) dp[5], dp[6]

dp[5]와 dp[6]도 마찬가지로 같은 방식으로 채우게 된다면 아래 표와 같이 채워진다.

dp	3	4	5	6
1	0	0	0	13
2	0	8	8	13
3	6	8	8	13
4	6	8	12	13

3. 수용가능한 물건이 여러개일 경우

이 문제의 해당 예제에서 가장 중요한 부분은 dp[7] 일때다. 이전까지는 하나의 물건만 수용가능했기 때문에 신경쓰지 않았지만
dp[7]인 경우 부터는 두 개 이상의 조합이 가능하기 때문이다.

dp	3	4	5	6	7
1	0	0	0	13	13
2	0	8	8	13
3	6	8	8	13
4	6	8	12	13

1) dp[7], i = 1 일때

i = 1 일때를 보면 (W1, V1)은 (6, 13) 이었다. 이렇게 될 경우 두 가지 방식으로 구성할 수 있다.

무게가 7인 물건
무게가 6인 물건 + 무게가 1인 물건

이 말은 곧 dp[7 - W[1]] 인 dp[1]의 이전 i값( i = 0 일때) 에 대한 값 + W[1] 과 i = 0 일때의 dp[7]을 비교하는 것이다.

i = 0일때는 주어진 배열의 범위 밖이기 때문에 0이 된다.

dp[1] + W[1] = 13이고 i = 0 일때 dp[7] = 0 이기 때문에 13이 저장된다.

2) dp[7], i = 2 일때

i = 2 일때의 물건은 (4,8) 이다.
일단 이전 값인 13을 가지고 오고 7-W[2] 무게에 대한 이전 i 값, 즉 3이고 3이라는 무게에 대응되는 i = 1일 때의 값은 0이다.

이 둘을 합하면 8이 되고 8과 13 중 최댓값을 고르기 때문에 13이 저장된다.

dp	3	4	5	6	7
1	0	0	0	13	13
2	0	8	8	13	13
3	6	8	8	13
4	6	8	12	13

3) dp[7], i = 3 일때

i = 3 일때의 물건은 (3, 6) 이다.

이전 값은 i = 2 일때의 dp[7]의 값이기 때문에 13이고
다른 조합 방법은 7 - W[3]인 4에 대응되는 i = 2의 가치는 8 이기 때문에 8 + V[3] 인 14가 된다.

따라서 14가 13보다 크기 때문에 i = 3일때의 dp[7]의 값은 14로 저장된다.

dp	3	4	5	6	7
1	0	0	0	13	13
2	0	8	8	13	13
3	6	8	8	13	14
4	6	8	12	13

4) dp[7], i = 4 일때

이전 탐색 값인 14와 7 - W[4] 인 2에 해당하는 값인 0과 V[4]를 합하면 12인데
14가 12보다 크기때문에 14로 저장된다.

dp	3	4	5	6	7
1	0	0	0	13	13
2	0	8	8	13	13
3	6	8	8	13	14
4	6	8	12	13	14

이러한 원리로 점화식을 만들면 다음과 같다.

f(i, k) = \begin{cases} 0 & \text{if } i = 0, k = 0 \\ f(i - 1, k) & \text{if } W_i > k \\ \max(f(i - 1, k - W_i) + V_i, f(i - 1, k)) & \text{if } 0 < i \text{ and } W_i \leq k \end{cases}

코드

이러한 조건으로 코드를 작성하면 아래와 같다.

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

public class Main_12865 {
    static int n, k;
    static int[] W;
    static int[] V;

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

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        dp = new int[n + 1][k + 1];

        W = new int[n];
        V = new int[n];

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

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                if (W[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i - 1]] + V[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

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

    }
}