백준 12865 [평범한 배낭]

문제

 

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

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

---

 처음 이 문제를 봤을때 dfs방식을 이용하여 문제를 풀었으나 시간초과가 발생했다. 최대한 경우의 수를 줄여서 dfs를 최적화 했지만 7%까지가 최선이었고 결국 시간초과의 벽에 부딪혔다.

 

 알고보니 이 문제는 조합 최적화문제로 DP를 이용하여 푸는 문제였다. 하지만 늘 풀어왔던 DP랑은 느낌이 달라서 이해하는데 오래걸렸다. 우선 다음과 같은 테스트케이스를 통해 어떤 방법의 DP로 풀었는지 표를 통해 확인해 보자.

(사실 백준문제에 있는 테스트케이스를 사용하려 했으나 실수로 잘못 옮겨적어서 테스트케이스가 바뀌었다)

 

[테스트케이스]

5 7

4 7

6 13

4 8

3 6

5 12

 

테스트케이스에서 주어진 값을 W와 V배열에 담아보면 다음과 같다.

i	0	1	2	3	4	5
W[i] (무게)	0	4	6	4	3	5
V[i] (가치)	0	7	13	8	6	12

 

i는 i번째 물건이고 W[i]는 i번째 물건의 무게, V[i]는 i번째 물건의 가치를 나타낸다.

이를 가지고 dp라는 2차원 배열을 만들어보자.

(i) \ (w)	0	1	2	3	4	5	6	7 (= K)
0	0	0	0	0	0	0	0	0
1	0
2	0
3	0
4	0
5 (= N)	0

dp배열은 세로축을 i번째 물건을 나타내는 i값, 가로축을 배낭에 들어갈 수 있는 무게들인 w값으로 나타낸다. 이때 w의 최댓값은 문제에서 주어진 가방에 넣을 수 있는 최대 무게 K이다. 우선 위와같이 i == 0 or w == 0인경우는 0으로 놔둔다. 그리고 i = 1인 경우부터 보자.

 

 i = 1인경우부터 본다는 뜻은 i = 1인 물건 1개만 있을 때 가방에 무게 w만큼 담을 수 있는 경우, 가방안의 가치의 최댓값을 dp배열(표)에 채워가는 것이다. i = 1인 물건의 무게가 4 가치가 7이므로 w가 3보다 작을 때는 가치가 0이고 w가 4이상일 때는 물건 i =1 이 담길 수 있으므로 가치가 7이돼서 표가 다음과 같이 바뀐다.

(i) \ (w)	0	1	2	3	4	5	6	7 (= K)
0	0	0	0	0	0	0	0	0
1	0	0	0	0	7	7	7	7
2	0
3	0
4	0
5 (= N)	0

 

i = 2인경우를 보면 이번엔 물건 i = 1과  i = 2로 가방에 무게 w만큼 담을 수 있는 경우, 가방안의 가치의 최댓값을 dp배열에 채워간야 한다. 이때 i = 1을 고려해야해서 dp[1]의 값들을 고려하여 표를 채워야한다. 따라서 만약 w > W[2]인 경우엔 i = 2인 물건을 가방에 담지 못하므로 dp[1]의 값을 그대로 가져온다(i = 1인 경우와 동일한 결과). 하지만 만약 w <= W[2]인 경우에는 i = 2인 물건을 가방에 담을 수 있으므로 i = 2인 물건을 가방에 담을 때와 dp[1]의 결과를 비교하여 더 가치가 높은 경우를 dp에 기록한다. 즉 w <= W[2]의 경우 dp[2][w]는 dp[1][w] (i = 2 물건이 안들어간 경우) 와 dp[1][w - W[2]] + V[i] (i = 2 물건이 들어간 경우) 중 큰 값으로 들어간다. 이를 토대로 표를 작성해보면 다음과 같다.

 

(i) \ (w)	0	1	2	3	4	5	6	7 (= K)
0	0	0	0	0	0	0	0	0
1	0	0	0	0	7	7	7	7
2	0	0	0	0	7	7	13	13
3	0
4	0
5 (= N)	0

 

이와같은 방법으로 dp[2] 가 i = 1, i = 2인 물건들을 고려한 결과이므로 dp[3]은 i = 1, i = 2, i = 3을 고려한 결과를 저장한 배열이 될 것이고 이렇게 표를 다 작성하면 다음과 같은 표가 나온다.

(i) \ (w)	0	1	2	3	4	5	6	7 (= K)
0	0	0	0	0	0	0	0	0
1	0	0	0	0	7	7	7	7
2	0	0	0	0	7	7	13	13
3	0	0	0	0	8	8	13	13
4	0	0	0	6	8	8	13	14
5 (= N)	0	0	0	6	8	12	13	14

 

표를 직접 한번 작성해보면 어떤 알고리즘인지 이해가 될 것이다. 꼭 한번씩 작성해보면 좋겠다.

 

그럼 위의 DP를 코드로 구현해본 결과를 보자.

import java.io.*;
import java.util.*;
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[] W = new int[N + 1];
        int[] V = new int[N + 1];
        int[][] dp = new int[N + 1][K + 1];
        for (int i = 1; i < N + 1; i++)
        {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            W[i] = w;
            V[i] = v;
        }
        for (int i = 1; i <= N; i++){
            for (int w = 1; w <= K; w++){
                if (W[i] > w)
                    dp[i][w] = dp[i - 1][w];
                else
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - W[i]] + V[i]);
            }
        }
        System.out.println(dp[N][K]);
    }
}

 위에서 살펴본 내용과 같은 내용이므로 for문안에 if문과 else문의 내용만 한 번 더 짚고 넘어가면 될 것같다.

 if의 조건문은 만약 가방에 w만큼만 담는 다고 했을때 i번째 물건의 무게가 w보다 크면 i번째 물건을 담지 못하므로 dp[i][w]의 값은 이전에 구해놓은 dp[i - 1][w]와 같은 값이 된다.

 만약 W[i] <= w라서 가방에 i번째 물건을 넣을 수 있는 경우,  i번째 물건을 넣지 않은 경우인 dp[i - 1][w]와 i번째 물건을 넣은 경우인 dp[i - 1][w - W[i]] + V[i] (이전에 구해놓은 값들 중 w = w - W[i]일때의 가치와 i번째 물건의 가치 V[i]를 더한 값)중 더 큰 값을 dp[i][w]에 넣는다. 

---

reference

 - https://st-lab.tistory.com/141