백준 12865번 평범한 배낭

평범한 배낭은 배낭의 최대 무게에 맞게 주어진 물건을 넣었을 때 얻을 수 있는 가치의 최대합을 구하는 문제다.

 

문제의 이름은 '평범한' 배낭이지만 실상은 전혀 평범하지 않은 문제다..

 

n번째 물건의 무게를 W(n), 가치를 V(n) 이라고 한다면 다음과 같이 나열할 수 있다.

W(1), V(1) = 6, 13
W(2), V(2) = 4, 8
W(3), V(3) = 3, 6
W(4), V(4) = 5, 12

 

이를 활용해 가방에 담을 수 있는 최대 무게에 따른 1~4번 까지 물건과 그 때의 최대 가치를 표로 그려보면 몇 가지 규칙을 발견할 수 있다. (칸에 담기는 숫자의 의미는 최대 가치다.)

 

※ 참고로 세로줄은 n번 물건까지 탐색했다는 의미이다.

물건 (W, V)	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
1 (6, 13)	0	0	0
2 (4, 8)	0	0	0
3 (3, 6)	0	0	0
4 (5, 12)	0	0	0

 

가방의 최대 수용 무게가 0kg부터 2kg까지는 담을 수 있는 물건이 없으므로 그 가치도 모두 0이다.

 

물건 (W, V)	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
1 (6, 13)	0	0	0	0
2 (4, 8)	0	0	0	0
3 (3, 6)	0	0	0	6
4 (5, 12)	0	0	0	6

 

4번 물건을 3kg 가방에 담을 때의 최대 가치도 6이다. 앞서 말한대로 세로줄은 n번 물건까지 탐색한다는 의미이기 때문이다. 즉, 3번째 물건까지 탐색했을 때, 최대 수용 무게를 초과하지 않고 물건을 담을 수 있어 그 가치인 6이 저장되었다. 그 다음에 4번째 물건을 담을 수 있는지 탐색하게 될텐데, 최대 수용 무게를 초과해 4번째 물건은 담을 수 없고 이전 물건에 대해 탐색했던 값을 그대로 갖고 있게 된다.

 

마찬가지로 4kg와 5kg도 채운다. 5kg에서는 4번째 물건을 담을 수 있으므로 가치 12가 채워진다. 6kg에서도 마찬가지다.

 

물건 (W, V)	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
1 (6, 13)	0	0	0	0	0	0	13
2 (4, 8)	0	0	0	0	8	8	13
3 (3, 6)	0	0	0	6	8	8	13
4 (5, 12)	0	0	0	6	8	12	13

 

6kg 까지는 두 개 이상의 조합으로 무게를 채울 수 없었기 때문에 간단히 채울 수 있었지만, 7kg 부터는 물건을 조합할 수 있다.

 

물건 (W, V)	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
1 (6, 13)	0	0	0	0	0	0	13	13
2 (4, 8)	0	0	0	0	8	8	13
3 (3, 6)	0	0	0	6	8	8	13
4 (5, 12)	0	0	0	6	8	12	13

 

먼저 이전과 마찬가지로 이전 물건의 가치값을 가져온다. 그러나, 0번째 물건은 없으므로 무게와 가치가 모두 0이다. 그리고 1번째 물건에 대해 탐색을 한다면 가능한 무게와 가치는 6과 13이었다. 그럼 2가지 방식으로 구성할 수 있게 된다. 

1. 무게가 7인 물건을 담는다. (현재 예제에서는 불가능하다)
2. 무게가 6인 물건 + 무게가 1인 물건을 조합한다.

즉, 가방의 최대 수용 무게가 1kg 이었을 때 0번째 물건을 담는 경우에 대한 최대 가치와 1번째 물건의 가치를 더한 값과 가방의 최대 수용 무게가 7kg이었을 때 0번째 물건을 담았을 경우에 대한 최대 가치를 비교하는 것이다. 이 때는 13보다 0이 더 크기 때문에 13이 저장된다.

 

수식으로 나타내면 이렇다.

dp[1][7] = Math.max( dp[0][7 - W(1)] + V(1), dp[0][7] )

 

물건 (W, V)	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
1 (6, 13)	0	0	0	0	0	0	13	13
2 (4, 8)	0	0	0	0	8	8	13	13
3 (3, 6)	0	0	0	6	8	8	13
4 (5, 12)	0	0	0	6	8	12	13

 

다음 값도 13이다. 일단 이전 물건에 대한 최대 가치인 13을 가져온다. 그리고 7-W(2) 무게에 대한 이전 값인 3kg, 1번째 물건일 때의 최대 가치는 0이다. 이것과 2번째 물건의 가치인 8을 더하면 8이 되고, 8과 13 중 최댓값은 13이므로 13이 된다.

dp[2][7] = Math.max( dp[1][7 - W(2)] + V(2), dp[1][7] )
//                   ----------------------  --------
//        최대 가치 :           8                13

 

물건 (W, V)	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
1 (6, 13)	0	0	0	0	0	0	13	13
2 (4, 8)	0	0	0	0	8	8	13	13
3 (3, 6)	0	0	0	6	8	8	13	14
4 (5, 12)	0	0	0	6	8	12	13	14

 

3번째 물건에서도 마찬가지다. 먼저 최대 수용 무게가 7kg일 때 2번째 물건까지 담았을 경우 최대 가치 13을 가져온다. 그리고 다른 조합 방법을 살펴보면 3번째 물건은 무게가 3kg이고 가치가 6이다. 이제 남은 무게 4kg에서 두번째 물건까지 담았을 때 최대 가치는 8이다. 즉, 6 + 8 = 14가 되고, 이전 최대 가치인 13보다 크므로 14를 저장한다.

 

그 다음 4번째 물건을 탐색할 때도 마찬가지로 14가 가장 큰 최대 가치이므로 14를 갖게 된다.

 

이제 2가지 경우에 대해 수식으로 정리할 수 있다. (아래 예문은 자바 문법에 맞게 작성하지 않았다.)

1. 지금 탐색중인 물건을 담을 수 없을 경우: W(i) > k
	dp[i][k] = dp[i - 1][k]
    
2. 지금 탐색중인 물건을 담을 수 있는 경우: W(i) <= k
	dp[i][k] = Math.max( dp[i - 1][k], dp[i - 1][k - W(i)] + V(i) )

 

이를 코드로 구현하면 다음과 같다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static Integer[][] dp;
    static int[] W; // weight
    static int[] V; // value
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int K = in.nextInt();

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

        for (int i = 0; i < N; i++) {
            W[i] = in.nextInt();
            V[i] = in.nextInt();
        }

        dp = new Integer[N][K + 1];

        System.out.println(mostValue(N-1, K));

    }

    public static int mostValue(int i, int k) {

        if (i < 0) {
            return 0;
        }

        if (dp[i][k] == null) {

            if (W[i] > k) {
                dp[i][k] = mostValue(i - 1, k);
            } else {
                dp[i][k] = Math.max(mostValue(i - 1, k), V[i] + mostValue(i - 1, k - W[i]));
            }
        }
        return dp[i][k];
    }
}