[Java] 백준(골드-5) 12865번 - 평범한 배낭

문제 풀이

---

유명한 배낭 문제 중 하나인 이번 문제는, 조합 최적화 문제로 동적 계획법(DP)로 해결해야 한다.

아이디어 도출

배낭 문제의 경우 짐을 쪼갤 수 있는 문제(Fraction Knapsack Problem)와 짐을 쪼갤 수 없는 문제(0/1 Knapsack Problem)로 나눠진다. 알고리즘 또한 다르게 적용하는데, Fraction Knapsack Problem은 그리디 알고리즘을, 0/1 Knapsack Problem의 경우 DP를 사용한다.

이번 문제는 짐을 쪼갤 수 없는 배낭문제이기에 DP로 풀어야 한다. N개만큼의 무게와 가치들을 토대로 수용가능한 최대 무게를 구하기 위한 규칙을 살펴보자.

i/dp	0	1	2	3	4	5	6	7
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

위 표를 보면, i에 따른 무게와 가치별로 누적 탐색해가며, 수용가능한 무게(dp)에 따라 최대 가치를 구해보았다. 이떄, DP를 통한 메모이제이션을 이용해 이전 i값에 대한 값을 바로 반환할 수 있도록 구현하는 것이 중요하다.

표에서 볼 수 있듯이, 우리는 수용가능한 무게가 7일 경우 6+8=14 의 값이 가장 큰 가치 값으로 저장되어 이를 구해야 하는 것을 알 수 있다. 이를 위한 점화식은 다음과 같다.

점화식

• DP[i][k] = max(DP[i-1][k], DP[i-1][k - W[i]] + V[i])

필자는 재귀함수를 이용한 Top-Down 방식으로 재귀 로직을 구현하였다. 재귀 호출을 통해서 현재 물건에 추가적으로 다른 물건을 담을 수 있는지 살피고, 위 점화식을 토대로 최대 가치가 되는 값을 DP 테이블에 갱신해나가는 방식이다.

간단하게 문제 풀이를 위한 아이디어를 정리해보자.

1. 2차원 배열인 DP 테이블과 1차원 배열인 무게(W), 가치(V) 배열을 선언한다.
2. DP 테이블은 DP[N][K+1]로 초기화, 입력값을 통해 W, V 배열에 값을 삽입한다.
3. 재귀함수를 호출하여 메모이제이션된 값이면 바로 값을 반환한다.
4. 메모이제이션 되지 않은(탐색하지 않은) 위치라면, 현재 물건을 추가로 담을 수 있는지, 없는지 확인한다.
5. 현재 물건을 추가로 담을 수 없다면, 현재 물건의 가치를 저장한다.
6. 현재 물건에 추가로 담을 수 있다면, 앞서 구한 점화식을 적용하여 더 큰 가치 값을 DP 테이블에 갱신하고 반환한다.

W, V 배열은 인덱스가 0부터 시작하기 때문에 i=0일 때를 고려해야 한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    // DP 테이블 선언
    static Integer[][] DP;

    // 물건의 무게와 가치를 담을 W, V 배열 선언
    static int[] W;
    static int[] V;

    public static void main(String[] args) throws IOException {

        try (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());

                // 2차원 DP 테이블 초기화
                DP = new Integer[N][K+1];

                // 무게와 가치를 담기 위한 1차원 배열 초기화
                W = new int[N];
                V = new int[N];

                // 무게와 가치를 N번만큼 입력받는다.
                for(int i=0; i<N; i++) {
                    st = new StringTokenizer(br.readLine());
                    W[i] = Integer.parseInt(st.nextToken());
                    V[i] = Integer.parseInt(st.nextToken());
                }

                // DP 테이블을 갱신하기 위해 Top-Down 방식의 재귀 호출
                int result = knapsack(N-1, K);
                bw.write(result+"\n");
                
                
        }

    }

    public static int knapsack(int i, int k) {
        if(i < 0) {
            return 0;
        }   
        // 탐색하지 않았다면
        if(DP[i][k] == null) {
            // 현재 물건을 추가로 담지 못할 경우
            if(W[i] > k) {
                DP[i][k] = knapsack(i-1, k);
            }
            /**
             * 현재 물건을 담을 수 있는 경우
             * 이전 i값과 이전 i값에 대한 k-W[i]의 값 + 현재 가치(V[i]) 중에서 더 큰 값을 DP 테이블에 저장한다.
             */
            else {
                DP[i][k] = Math.max(knapsack(i-1, k), knapsack(i-1, k - W[i]) + V[i]);
            }
            
        }
        return DP[i][k];
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.