[JAVA] 백준 #12865 평범한 배낭 | 초보자도 이해할 수 있는 Knapsack Problem 풀이 방법 | Dynamic Programming

 

[JAVA] 백준 #12865 평범한 배낭

12865번: 평범한 배낭

🔒 문제

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

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

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

---

 

[0] Knapsack 알고리즘 구현을 위해 필요한 자료구조 선언 

우선 본격적인 알고리즘 풀이에 들어가기 앞서서 필요한 자료구조를 선언하고 입력받는 부분을 간단히 짚고 넘어가겠다.

 

 🔹변수 및 배열 선언부 / 입력값 저장

public class Main {
    static int N;
    static int limit;
    static int[] weight;
    static int[] value;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        limit = Integer.parseInt(st.nextToken());
        weight = new int[N+1];
        value = new int[N+1];

        for( int i = 1; i < N+1 ; i++ ){
            st = new StringTokenizer(bf.readLine(), " ");
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            weight[i] = W;
            value[i] = V;
        }

        dp = new int[N+1][limit+1];
        
        ....

 

우선 배낭 알고리즘을 다이나믹 프로그래밍으로 풀이하려면 메모제이션을 진행할 2차원 배열 DP 하나와, 입력으로 받는 물건의 가치, 무게를 각각 저장할 weight, value 배열을 선언해 준다. 

 

일단 자료 선언부에서 Knapsack Problem의 핵심을 간단히 설명하자면 현재 i 번째 물건을 담을 때 or i 번째 물건을 안담을 때 각각의 가방의 무게를 비교해서 더 큰 값으로 갱신해 나간다. 

그러므로 첫 번째 물건부터 N번째 물건까지 가방의 최대 무게가 1부터 limit까지 일 때 가치의 최댓값을 갱신해 나가면서 마지막에 dp [N][limit]에 저장된 값을 구하는 것이 목표이다. 자세한 내용은 아래 코드에서 설명하도록 하겠다.

 

자료구조 설명을 이어서 하자면,

 

- DP의 열(세로)에는 1부터 가방에 넣을 수 있는 무게의 최댓값인 limit까지를 담을 건데, 배열 선언 시 맨 앞 인덱스는 0이고 배열 크기를 limit으로 설정하면 배열의 마지막 인덱스는 limit -1 이기 때문에 limit를 인덱스에 포함하기 위해 열의 크기를 limit + 1로 지정해 준다.

 

- DP 배열의 행(가로)은 각 물건의 인덱스라고 생각하면 되는데, 행의 인덱스 i에 대해 weight [i] 배열과 value [i] 배열에 i로 접근하면 하나의 물건의 무게와 가치를 각각 가져올 수 있다. 행의 크기도 N + 1로 지정해 줬는데 그 이유는 뒤에서 코드와 함께 설명하도록 하겠다. 

우선 각 자료형을 선언하고, 입력값을 담아주면 위와 같은 모습이다. dp [][]의 모든 배열의 값은 0으로 초기화되어 있는데, 실질적으로 for문에서 갱신이 일어나지 않는 곳은 0으로 그대로 두고 for문에서 훑을 부분은 빈칸으로 두었다. 

또한 weight, value 배열의 첫 인덱스는 원래 0인데 사용하지 않기 때문에 표에서 생략했다.

 

 

🔹DP 구현부

        for( int i = 1; i < N + 1 ; i++ ){
            for( int j = 1; j < limit + 1; j++ ){
                dp[i][j] = dp[i-1][j];

                if( weight[i] <= j ) {
                    dp[i][j] = Math.max( dp[i][j], dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

일단 코드는 꽤 간단한데 이게 어떻게 작동하는 건지 제대로 뜯어보자

 

[1] i = 1 일 때

dp[i][j] = dp[i-1][j];

먼저 dp 구현부 3번 줄에서 이전 인덱스 줄을 그대로 복붙해온다. 이는 'i번째 물건을 담지 않았을 때 최댓값'들을 일단 가져와서 배열을 초기화해 두는 것이라고 생각하면 된다. dp는 1 -> 2 ->.... ->  N 순서로 값을 갱신해 나가기 때문에 현재 인덱스 i의 바로 위에 있는 i - 1 행에 있는 값들이 현재 최댓값을 담고 있는 것이다. 

 

현재 i는 1이니까 i=0일 때 바로 위의 값을 그대로 복붙해온다. 이때 여기서 dp의 열의 크기를 N + 1로 지정한 이유가 나오는데, 만약 dp의 크기를 N으로 지정했으면 첫 번째 인덱스가 0부터 시작한다. 그럼 i-1 값은 -1로 존재하지 않으므로 3번 줄 초기화 작업에 대해 IndexOutOfRange 오류가 발생한다. 따로 i = 0일 때를 조건문을 써서 예외처리 해 줄 수도 있겠지만 애초에 배열의 크기를 1 크게 잡는 것이 훨씬 수월하므로 크기를 N + 1로 지정했다.

 

if( weight[i] <= j ) {
    dp[i][j] = Math.max( dp[i][j], dp[i-1][j-weight[i]] + value[i]);
}

자 이제 초기화가 끝났으면 i번째 물건을 넣을지 말지를 결정해 보자. 5번 줄에서 현재 물건의 무게 weight [i]와 현재 가방의 최대 무게인 j를 비교하고 있다. 여기서 만약 j가 더 크거나 같다면 현재 물건을 넣을 수 있다는 말이다. 

다만 실제로 넣을지 말지는 물건을 넣지 않았을 때의 최댓값 즉, 현재 dp [i][j]의 값 <-> 현재 물건을 담았을 때의 가치를 비교해서 물건을 담았을 때가 크다면 물건을 담았을 때 가치값으로 갱신해 준다. 

일단 첫 번째 물건의 무게는 6이기 때문에 j = 1, 2, 3, 4 ,5에 대해선 갱신이 일어날 여지가 없다. 

그런데 j = 6일 때 물건이 들어갈 수 있는 여지가 생긴다. 그럼 여기서 코드 5번 줄 for문에 걸리므로 물건을 넣을지 말지 비교하는 과정을 진행한다. 

우선 물건을 넣지 않을 경우 가치는 현재 dp [0][6]에서 가져온 값인 0이다.

그럼 넣는 경우에는 { ( ( 현재 무게 한계점 = 6 )에서 ( 현재 물건 무게 = 6 ) ) 뺀 무게의 최대 가치  + 현재 물건의 가치 }와 같다. 

현재 에시에서 무게 한계점과 물건 무게가 같아서 헷갈리는데, 단순히 말하면 만약 j = 10이라면 현재 물건을 넣었을 때 남은 무게는 4이다. 그러니까 남은 무게인 4의 최대 가치 + 현재 물건의 가치 이렇게 두 개를 더하면 넣는 경우의 가치를 구할 수 있는 것이다. 

 

그래서 이 두 개를 비교해 보면 당연히 현재 모든 배열의 값이 0이니까 물건을 넣는 것이 최댓값임을 알 수 있다. 그러므로 갱신하면 dp [1][6], dp [1][7]에 13이 들어간다. 

 

 

[2] i = 2 일 때

이번에는 두 번째 물건에 대해서 확인해 보자. 우선 두 번째 물건에 대해서도 dp [i-1][j] 값을 그대로 가져오는 과정이 진행된다.

그다음엔 갱신을 진행하는데 여기서 j = 4부터 현재 물건을 넣을 수 있으므로 갱신된다. j = 5도 같은 방식으로 현재 물건의 가치로 갱신된다.

 

이제 j = 6일 때를 보면, 현재 물건을 담는 경우 현재 물건의 가치는 8, 6 - 4인 2의 무게일 때 최대 가치는 dp [i-1][2] 즉 0이므로 8이다. 그럼 8과 dp [i][j]를 비교해 보면 물건을 담지 않는 경우의 가치인 13이 더 크기 때문에 갱신은 일어나지 않는다. j = 7일 때도 같은 이유로 갱신이 발생하지 않는다. 

 

이러한 원리로 반복을 하다 보면 마지막 dp [N][limit]에 담기는 값은 14이다.

 

🔹 전체 코드 

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

public class Main {
    static int N;
    static int limit;
    static int[] weight;
    static int[] value;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        limit = Integer.parseInt(st.nextToken());
        weight = new int[N+1];
        value = new int[N+1];

        for( int i = 1; i < N+1 ; i++ ){
            st = new StringTokenizer(bf.readLine(), " ");
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            weight[i] = W;
            value[i] = V;
        }

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

        for( int i = 1; i < N + 1 ; i++ ){
            for( int j = 1; j < limit + 1; j++ ){
                dp[i][j] = dp[i-1][j];

                if( weight[i] <= j ) {
                    dp[i][j] = Math.max( dp[i][j], dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

        System.out.println(dp[N][limit]);
    }

}