[백준][Gold5] 12865 - 평범한 배낭 - JAVA

[문제]

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

12865번: 평범한 배낭

 

처음에 완전탐색으로 풀었는데 시간초과가 떴다.  찾아보니 배낭문제(knapsack problem)는 dp를 응용하는 아주 유명한 문제라고 한다. 

 

dp, 즉 메모이제이션을 이용하기 위해서는 값을 저장할 테이블을 정의해야 한다. 

다음과 같은 이차원 배열을 정의하겠다. 

dp[i][j] = value 

- i : 1 ~ i 까지의 아이템을 의미 

- j : 배낭에 넣을 수 있는 최대 무게 

- value : 배낭에 넣을 수 있는 최대 무게에 상응하는 가치 

 

그림을 보면 이해가 쉬울 것이다. 

 

1. 이차원 배열에서 행은 아이템의 개수에 상응한다. 

행이 1이면 아이템 1이 존재한다는 뜻이다. 

 

그럼 행이 2이면 아이템 2만 존재한다는 뜻일까?

아니다. 행이 2이면 아이템이 1~2까지 존재한다는 뜻이다. 그리고 dp[2][j]는 아이템이 1~2까지 있고, 배낭에 채울 수 있는 최대 무게가 j일 때 최대 가치를 의미한다.

 

마찬가지로 행이 3일때는 아이템이 1~3까지 있다는 뜻이고 4일 때는 아이템이 1~4까지 있다는 뜻이다.  

 

2. 먼져, 아이템이 0개 일때는 채울 수 있는 무게가 하나도 없으므로 배열에 모두 0이 들어간다. 

 

3. 다음 아이템 1이 있을 때를 보자. 

아이템 목록을 보면 아이템 1의 무게는 6이고 가치는 13이다. 

 

아이템의 무게가 6이므로 배낭에 채울수 있는 최대무게가 0~5일 때까지는 아이템 1을 넣을 수가 없다. 

비로소 6부터 넣을 수 있고 가치는 13으로 채워진다. 

 

이쯤 다시 테이블의 의미를 정리해보면, dp[1][6] = 13은 이런의미이다. 

"아이템이 1까지만 있고, 배낭에 채울 수 있는 최대무게가 6일 때 최대가치는 13이다."

4. 아이템이 1~2까지 있을 때를 보자. 

아이템 1,2 모두 최대무게가 0~3일 때는 들어갈 수 없다. 

그리고 최대무게가 4인 경우에는 아이템 1은 들어갈 수 없지만 2는 들어갈 수 있다. 

 

이걸 코드로 어떻게 표현할까?

 

아이템 1,2가 있을 때 결국 아이템들을 선택하는 경우는 다음과 같이 나눌 수 있다. 

1) 아이템 2를 포함하지 않는 경우 ({1})

2) 아이템 2를 포함하는 경우 ({2}, {1,2})

 

1번 경우부터 보면 아이템 2를 포함하지 않을 때, 즉 아이템이 1만 있고, 최대무게가 4일 때 최대가치는 뭐였을까?

맞다. 바로 위에서 구했던 dp[1][4] = 0 이다. 즉 앞서 구한 dp 값을 이용할 수 있는 것이다. 

 

그다음 2번 경우를 보자.

아이템 2를 포함하면 item[2] = (무게:4, 가치:8) 를 배낭에 담으므로 배낭에는 무게 4가 채워지고 가치가 8이 된다. 

그러면 그 이후에는? 

최대 무게가 4인데, 아이템2 무게가 4이므로 더 이상 채울 수 있는 무게가 없다. 즉, 남은 무게는 0이다. 

그리고 또 하나, 남은 무게가 0이든, 10이든, 100이든간에 이미 아이템 2는 배낭에 담겼다. 그러면 이제 남은 무게는 아이템 2를 제외하고 남은 아이템으로 채워야 한다. 즉 아이템 1로 채워야 한다. 그럼 결국 또 구해야 하는건?

맞다. dp[1][0] 이다. (dp[2를 제외한 아이템들][남은 무게])

결과적으로 아이템 2를 포함했을 때 최대 가치는 8(아이템 2의 가치) + dp[1][0] = 8 이다. 

 

그럼 그럼 그럼!

1) 아이템 2를 포함하지 않는 경우 ({1}) -> 최대가치 : 0

2) 아이템 2를 포함하는 경우 ({2}, {1,2}) -> 최대가치 : 8

 

1,2중에 더 큰값이 최대가치이므로 dp[2][4] = 8 이 된다. 

 

dp[2][5]도 마찬가지...

 

그럼 최대무게 6일 때도 한번 계산해볼까?

위와 똑같이 복습해보겠다. 

1) 아이템 2를 포함하지 않는 경우 ({1})

2) 아이템 2를 포함하는 경우 ({2}, {1,2})

 

1의 경우는 dp[1][6] = 13

 

2의 경우는 8 + dp[1][2] = 8 + 0 = 8;

왜 dp[1][2] 냐고? 최대 무게가 6일 때 아이템 2를 선택하여 담았으므로 남은 무게는 2이고 2를 제외하고 선택할 수 있는 아이템은 1이므로.  

 

즉, max(13, 8) = 13이 최대가치이다. 

 

5. 아이템이 1~3까지 있을 때를 보자. 

이제 위에서 사용한 방법대로 최대무게 0 ~ 6까지는 채울 수 있다. 

 

이제 최대무게 7일 때를 한번 구해보자! 여기가 중요하다. 

당연히 방식은 위와 동일하다. 아이템 1~3까지 있으므로 아이템을 뽑을 수 있는 경우는 다음과 같이 나눈다. 

1) 아이템 3을 포함하지 않는 경우

2) 아이템 3을 포함하는 경우

 

1번 경우 아이템 3을 포함하지 않는 경우는 dp[2][7] = 13일 것이다. 

그 다음! 2번 경우 아이템 3을 포함하면

 

배낭에 무게 3이 채워지고 가치는 6이 된다. 최대 무게가 7이므로 이제 남은 무게는? 

아이템 3이 채워졌으므로 당연히 남은 무게는 4다. 

그럼 이제 남은 무게 4를 아이템 1~2로 채워야겠지. 그러면 dp[2][4] 를 구해야겠지. 

즉, 6(아이템 3의 가치) + dp[2][4] = 6 + 8 = 14 다!!!

 

결과적으로, max(13, 14)로 최대가치는 14가 된다. 

6. 아이템 1~4일 때도 동일한 방법으로 구하면 다음과 같이 표를 모두 완성할 수 있다. 

7. 

문제에서 구하라고 하던게 뭐였더라?

아이템 1~4개 있고, 최대 무게 7일 때 최대 가치였다. 즉, dp 가장 마지막 데이터 dp[4][7]=14를 출력하면 문제의 정답이다. 

 

----

처음에 완전탐색으로 풀고 시간초과가 뜬 후 해답을 보았을 때 이게 dp로 풀린다고..? 하고 1차 좌절했다. dp로 푸는것은 상상도 못했기 때문. 그리고 풀이를 보면 2차 좌절했다. 수많은 블로그를 봐도 완전히 쏙 이해되어 내것이 되지가 않았기 때문.

하지만 직접 테이블을 그려보고 차분히 생각해보고 원리를 이해하려고 노력하니 어느새 이해할 수 있었다.

뭐 별 수 없는 것 같다. 이해가 될 때까지 내가 스스로 노력하는 수밖에는.

그러니 혹시 아직도 이해가 안되는 분들이 계시다면 좌절하지 말고 끝까지 공부해보세요 ㅠ 화이팅 ㅠㅠ!

 

[code]

package com.algorithm.baekjoon.gold5;

import java.io.*;
import java.util.StringTokenizer;

/**
 * 12865 - 평범한 배낭
 */
public class Test11 {
    public static int[][] dp;

    static class Item {
        int weight;
        int value;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 물품의 수
        int K = Integer.parseInt(st.nextToken()); // 최대 무게

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

        Item[] items = new Item[N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            items[i] = new Item(w, v);
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (items[i].weight > j) { // 현재 아이템의 무게가 배낭에 넣을 수 있는 최대 무게보다 큼
                    dp[i][j] = dp[i - 1][j]; // 이전 dp값 넣기
                } else { // 현재 아이템의 무게가 배낭에 넣을 수 있는 최대 무게와 같거나 작음
                    int num1 = items[i].value + dp[i - 1][j - items[i].weight];
                    int num2 = dp[i - 1][j];
                    dp[i][j] = Math.max(num1, num2);
                }
            }
        }

        bw.write(dp[N][K] + "\n");
        br.close();
        bw.flush();
        bw.close();
    }
}