[백준] 12865 - 평범한 배낭

백준 바로가기

12865번: 평범한 배낭

---

평범한 배낭 문제는 DP 알고리즘으로 분류되며 대표적인 '냅색'(Knapsack) 알고리즘 문제라고 합니다. 위키백과

배낭 문제 - 위키백과, 우리 모두의 백과사전

천재가 아닌 이상 유형을 알지 않고선 풀기 힘든 문제라고 봅니다. 반대로 말하면, 유형을 반드시 이해하고 있어야 유사한 문제가 또 나와도 해결할 수 있습니다. 이번 글 부턴 문제를 단계로 나눠서 설명하겠습니다. 문제해결 메커니즘에 도움도 되고 다른 분들 이해에도 편할 것 같아서요.

1) 데이터 '틀'

문제에서 주어진 데이터를 어떤 틀로 담을 지 정하는 단계입니다. 이 문제에선 아이템 수: N, 한계 무게: K가 첫 줄에 주어지고 두 번째 줄부턴 각 아이템별 무게: W, 가치: V가 주어집니다. 단일 데이터인 N과 K는 int로 변수를 받고 다중 데이터 W과 V는 int[] 배열로 변수를 설정하겠습니다. 가장 중요한 정답을 담는 배열은 2차원 함수인 int[][] 배열에 담는데, 그 이유는 아래에서 설명해드리겠습니다. 

2) 문제해결 로직

냅색 문제의 로직은 1~n번째 아이템까지 반복문으로 돌면서 1~k 무게에서 최대 가치를 저장해 원하는 값을 최종으로 출력해주는 것입니다. 잘 이해가 되지 않으시죠? 로직의 요지는 '누적'에 있습니다. 점화식을 보면서 설명드리겠습니다.

        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j]; //i번째 물건을 선택하지 않았을 때
                if (j - w[i] >= 0)
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); //선택했을 때 최대 가치와 하지 않았을 때 최대가치를 비교
            }
        }

1행의 for문이 시작되는 지점은 n개의 아이템을 도는 반복문입니다. 2행의 중첩 for문은 1~ 한계 무게를 도는 반복문인데요 왜 1부터 시작하는지, 그리고 왜 dp는 2차원 배열을 사용했는지 알려드리겠습니다.

우선 dp 2차원 배열의 1차 index는(dp[i][j]) i번째까지 아이템을 말하며, 2차 index는(dp[i][j]) j무게를 뜻합니다. 따라서 배열에 들어가는 값은 뭐가될까요? 바로 i번째까지 아이템들로 j무게를 만들 때 가질 수 있는 최대 가치 V 입니다!

그리고 왜 j 무게를 1부터 시작하는지에 대해 말씀드릴게요. 바로 5행의 점화식과 연관이 되어있습니다. i번째 아이템을 넣기로 결정했다면 이라는 가정에서 출발합니다. 비교 대상은 우리가 지금까지 얻은 데이터에서 찾아야 하기 때문에 무조건 'i-1번째 아이템까지 경우의 수를 모두 고려한 상태' 입니다. 그래서 j무게를 만들 수 있는 최대가치V가 max인 값을 선택할 것인데, 비교 대상①(dp[i-1][j]) 은 i-1 번째 아이템까지 조합해서 만들 수 있는 최대 V이고 비교 대상 ②(dp[i-1][j - w[i]] + v[i])는 i번째 아이템을 선택했을 때 만들 수 있는 최대 V입니다.

비교 대상 ②에서 왜 j - w[i]를 하냐구요? 현재 최대 무게인 j를 만드려면, i-1번째에서 i의 무게만큼 뺀 무게일 때에 들어가야되기 때문입니다.

예를 들자면 제가 5kg인 노트북(가치:10)을 넣으려고 하는데 그 전까지 3kg인 아이패드(가치: 3)와 2kg인 크록스(가치:6)를 담은 상태라고 가정해봅시다. 그리고 현재 만들어야 하는 최대 무게(j)는 5kg입니다.

다시 점화식으로 돌아보자면 비교대상 ①(dp[i-1][j])의 최대 가치는 9입니다. 3kg인 아이패드와 2kg인 크록스를 모두 담았을 때무게가 5kg이며 가치가 9 이기 때문이죠. 그렇다면 비교대상 ②(dp[i-1][j - w[i]] + v[i])는 노트북을 넣었을 때인데, 무게가 5kg이니까 아이패드와 크록스 모두 뺐을 때만 넣을 수 있겠죠. 이를 식으로 표현하면 [j - 5kg(노트북)], 즉 무게가 0kg일때 넣어야 합니다.

이제 이해가 되셨나요? 그래도 이해가 되지 않는다면 주어진 코드를 38행부터 debug 하시면서 dp배열 값이 제어변수 i, j가 변화할 때 어떻게 변하는 지 보시는 것을 추천합니다. 저도 그렇게해서 이해했어요. 감사합니다 :)

3) 정답 코드

package baekJoon.week12;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BagPacking_12865 {
 
    static int[] v;
    static int[] w;
    static int[][] dp; //[i번째 아이템][무게]
    static int n;
    static int k;
    static int temp = 1;
    static int temp1;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        temp1 = n;
        k = Integer.parseInt(st.nextToken());
 
        v = new int[n + 1];
        w = new int[n + 1];
        dp = new int[n + 1][k + 1];
 
        while (temp1-- > 0) {
            st = new StringTokenizer(br.readLine());
            w[temp] = Integer.parseInt(st.nextToken()); //W
            v[temp] = Integer.parseInt(st.nextToken()); //V
            temp++;
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j]; //i번째 물건을 선택하지 않았을 때
                if (j - w[i] >= 0)
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); //선택했을 때 최대 가치와 하지 않았을 때 최대가치를 비교
            }
        }
 
        System.out.println(dp[n][k]);
 
 
    }
 
 
}