백준 알고리즘 12865번: 평범한 배낭 / 배낭 문제(Knapsack Problem)

문제 정보

---

12865번: 평범한 배낭

 

핵심

---

문제 이해

• 총 N개의 물건
• 각 물건은 무게(W), 가치(V)를 가짐 -> 해당 물건을 가지고 가면, V만큼 즐길 수 있음
• 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고다닐 수 있음

 

이를 통해 배낭에 넣을 수 있는 물건들의 가치 합의 최대를 구하는 문제

 

조건

• 물품 수(N) <= 100
• K <= 100,000 / W <= 100,000 / V <= 1,000

 

먼저, 나는 멍청하게도 DFS 로 모든 경우를 탐색해 보려고 했었다. 조건에 보이는 N의 범위가 100 이하였기 때문이다.

하지만 이는 틀린 생각은 아닐 수 있지만 효율적인 생각은 아닌 것은 확실했다. 몇 개를 골라야 하는지에 관해서도 정해진 건 없으며 모든 경우를 탐색하다가 시간초과가 발생할 것이 뻔했다

 

공부하던 도중, 배낭 문제(Knapsack Problem) 라는 알고리즘이 이미 사용되고 있다는 것을 알게 되었고 이번 문제는 해당 배낭 문제 그 자체인 문제였다.

단순하게 문제를 생각해 보면, 해당 물건을 배낭에 넣느냐/마냐 의 결정만으로 문제를 풀어갈 수 있다.

그리고 해당 물건을 넣었을 때 / 해당 물건을 넣지 않았을 때의 각각의 최대값의 최대값을 풀어가면 답을 도출할 수 있다.

이를 0-1 Knapsack Problem 이라고 한다고 한다.

 

초기 상태

예제 1번을 풀어가는 방식을 그림으로 설명하는 편이 좋을 것 같다. (N=4, K=7)

먼저 이차원 배열이 베이스가 된다.

각각의 행은 가방의 무게를 뜻한다. 총 7까지의 무게를 담을 수 있는 가방이기 때문에 0부터 7까지를 기록해 놨다.

각각의 열은 넣는 물품의 번호를 의미한다. 순서는 상관이 있지는 않고, 해당 번호를 인덱스로 한 물품의 (무게, 가치)를 다른 이차원 배열에 입력값으로 저장해 놓았다.

 

가방에 담을 수 있는 무게가 0일 때, 아무것도 담을 수 없기 때문에 0으로 채운다 (행)

어떠한 물품도 넣지 않았을 경우에는, 아무 가치가 없으므로 0으로 채운다 (열)

• 해당 작업은 Java에서 int형 2차원 배열을 생성할 때 모두 0의 초기값을 가지기 때문에 생략해도 된다

 

첫번째 물품(무게 6, 가치 13)을 가방에 넣어보자.

가방에 담을 수 있는 무게가 6이 되기 전까지는, 선택한 물품을 담을 수 없으므로 모두 0으로 채워질 것이다.

6 이상이 된다면 해당 물품을 1개씩 담을 수 있기 때문에 총 가치는 13이 된다.

 

두번째 물품(무게 4, 가치 8)을 가방에 넣어 보자.

가방의 무게가 4가 되기 전까지는 물건을 담을 수 없으니 0으로 채워주고,

4, 5에서는 해당 물건만 담을 수 있으니 현재 물품의 가치인 8을 넣어 준다

그 다음 가방 무게가 6이 되면, 두번째 물품을 넣는 것보다 두번째 물품을 안넣는 것(첫번째만)이 더 최대가 된다 (13 vs 8)

 

2번 물품을 담지 않았을 때의 최대는 바로 왼쪽 (dp[6][1])을 의미한다. -> 13

2번 물품을 담았을 때의 최대는 2번 물품의 가치(things[2]) + 2번 물품을 넣고 남은 가방으로 담을 수 있는 최대 가치(dp[2][1])을 의미한다.

• 따라서 13 vs 8 + 0 이므로 13이 들어간다

 

자, 여기서 점화식을 찾을 수 있었다.

dp[i][j] = Math.max(dp[i-1][j],
                        j >= things[i][0] ?
                        things[i][1] + dp[i-1][j-(things[i][0])] :
                        0);

dp[i-1][j] : 현재 위치에서 바로 왼쪽(자기 자신을 담지 않았을 때의 최대값)

가방의 무게가 현재 물품의 무게보다 크면 -> 현재 물품의 가치(things[i][1]) + 남은 가방으로 담을 수 있는 최대 가치(dp[i-1][j-things[i][0])

작다면 -> 0

 

Question

여기서 왜 남은 가방으로 담을 수 있는 최대 가치가 dp[i-1][~~] 인 것일까?

그건 바로 현재 물품을 선택한 경우에, 현재 물품을 하나 더 담을 수 없기 때문이다

만약 가방에 담을 수 있는 최대 무게가 4이고, 현재 물품의 무게가 2라면

현재 물품을 하나 선택하고 + 2로 담을 수 있는 최대 가치(현재 물품) 이 나올 수 있는 경우가 존재하기 때문이다.

 

짧게 설명했는데, 위 방식대로 dp 배열을 채워가다 보면 결국 답(dp[7][4]) 를 도출할 수 있게 될 것이다.

부족한 부분은 아래 Reference에 배낭 문제에 대해 공부하고 오거나, 코드를 보고 공부해도 좋을 것 같다.

 

풀이

---

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

public 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[][] things = new int[N+1][2];
        // things[0]: 해당 물건의 무게
        // things[1]: 해당 물건의 가치

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            things[i][0] = Integer.parseInt(st.nextToken());
            things[i][1] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[N+1][K+1];
        // i: 선택한 물품의 번호 (1~N)
        for(int i=1; i<=N; i++) {
            // j: 가방에 넣을 수 있는 최대 무게
            for(int j=1; j<=K; j++) {
                // 현재 선택한 물품보다 가방의 무게가 크면, 현재 물품을 고려하여 최대 가치를 선정
                // 아니면, 이전 물품에서 같은 가방의 무게일 때의 값을 대입
                dp[i][j] = Math.max(dp[i-1][j],
                        j >= things[i][0] ?
                        things[i][1] + dp[i-1][j-(things[i][0])] :
                        0);
            }
        }
        System.out.println(dp[N][K]);
    }
}

 

Reference

---

 

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

 

 

Source Code on GitHub

---