들어가며

배낭 문제(Knapsack Problem)는 조합 최적화 문제의 기본적인 문제 유형으로 동적 계획법(DP)을 이용해 풀 수 있습니다. 코딩 테스트에서 배낭 문제 혹은 냅색이라고 하면 바로 이 유형이구나 생각하면 됩니다.

0 - 1 배낭 문제

배낭 문제의 핵심은 각각 가중치(Weight)와 가치(Value)를 가진 집합이 주어졌을 때, 총 가중치의 한계 내에서 유지하면서 총 가치가 가장 커질 수 있도록 어떤 원소를 포함시킬 것인지 결정하는 것입니다. 쉽게 말해 10kg 용량 배낭에 [5kg, 5만원, 신발], [6kg, 4만원, 패딩], [4kg, 3만원, 속옷]이 있을 때 어떤 것들을 가져가야 용량에 넘치지 않으면서 최대 가치를 챙길 수 있는지 찾는 것입니다. 위 예시에서는 신발과 속옷을 챙기는 것이 8만원으로 가장 높은 가치를 가집니다.

배낭 문제는 가중치(Weight)와 가치(Value)가 있을 때, 집합의 원소를 조합해서 목표(Objective)를 최대화, 최소화 혹은 기타 조건을 주는 문제에서 사용할 수 있습니다. 이러한 원소들을 직접 주기도 하지만, 푸는 사람이 원소들을 배낭 문제의 형태로 정제해서 사용하도록 유도하는 경우가 많습니다. 즉, 많은 코딩 테스트 문제에서 다른 유형의 문제인 척 배낭 문제를 위장하는 경우가 많죠.

예를 들어, 앱 몇 개를 비활성화해야 할 때, 메모리를 X바이트 이상 확보하면서 비용 Y를 최소화하는 방법을 찾는 문제(목표를 최소화 하기), 기업의 개수와 투자 액수에 따른 이익만 주고 이익금을 최대화하는 방법을 찾는 문제(원소를 만들어 내기), 아이들에게서 사탕을 빼앗을 때 아이들의 친구의 사탕까지 빼앗는데 이때 울음소리를 K이하로 유지하면서 최대한 빼앗을 수 있는 사탕의 개수를 찾는 문제(분리 집합 + 냅색) 등등이 있습니다. 추가적으로 목표를 최소화하거나 최대화하는 것이 아니라 경우의 수를 찾는 문제에서도 이 배낭 문제의 해결법이 활용될 수 있습니다.

이번 포스트에서 풀 문제는 가장 기초적인 문제인 평범한 배낭 문제입니다. 문제의 핵심은 무게 W와 가치 V를 가지는 N개의 물건(1 ≤ N ≤ 100)이 있을 때, 준서가 버틸 수 있는 무게 K내에서 총 가치의 최댓값을 구하는 문제입니다.

Approach 1. 완전탐색/백트래킹

가장 먼저 생각할 수 있는 방법은 역시 모든 물건들의 조합을 구하는 완전탐색이겠죠. 물건의 개수 N은 최대 100개가 될 수 있으므로 각각 담는다/담지 않는다로 구분하면 O(2^N)의 시간복잡도를 가집니다. 2^100 은 천문학적인 숫자이므로 비현실적인 풀이입니다. 백트래킹으로 무게 K를 넘는 경우를 가지치기한다고 해도 결과를 확신하기 어렵습니다.

Approach 2. 그리디

그리디하게 풀기

모든 경우의 수를 찾는 방법은 현실적으로 어렵기 때문에 다시 원점으로 돌아와 한 가지 아이디어를 적용해보겠습니다. ‘단위 무게 당 가치가 가장 높은 물건부터 가방이 꽉 찰 때까지 담으면 되지 않을까?’ 즉, 현재 상황에서 가장 최적인 답을 선택해 결과를 도출하는 그리디 알고리즘입니다. 위의 예를 다시 가져오면 [5kg, 5만원, 신발], [6kg, 4만원, 패딩], [4kg, 3만원, 속옷] 인 물건들이 있을 때, 각각 키로 당 가격은 1만원/kg, 0.67만원/kg, 0.75만원/kg이므로 신발과 속옷을 가방에 담으면 가장 최적화된 결과를 얻을 수 있습니다.

위의 방법대로 풀기 위해서는 각각 키로 당 가격을 계산한 다음, 정렬하고 하나씩 뽑으면서 가방의 무게 제한이 넘칠 때까지 담으면 되겠죠. 이 방법은 분말이나 액체 같이 물건의 일부를 쪼개서 담을 수 있는 경우에는 사용할 수 있습니다. 이를 연속적 배낭 문제(Continuous knapsack problem) 혹은 분할 가능 배낭 문제(Fractional Knapsack Problem)라고 합니다.

하지만 속옷이나 신발은 일부만 잘라서 가져갈 수 없겠죠. 따라서 그리디하게 풀면 다음과 같은 반례가 생깁니다.

그리디하게 풀 경우 생길 수 있는 반례

위의 예제를 수정해서 [5kg, 55,000원, 신발], [6kg, 60,000원, 패딩], [4kg, 39,000원, 속옷]이라면 단위 무게 당 가치는 각각 11,000원/kg, 10,000원/kg, 9,750원/kg이 됩니다. 그리고 배낭의 용량이 7kg라면, 그리디한 접근에서 단위 무게 당 가치가 가장 큰 물건인 신발을 넣어야 하지만, 정답은 무게 당 가치가 두번째로 큰 패딩을 넣어야 60,000원으로 최대 가치를 가질 수 있습니다.

즉, 항목을 분할할 수 없다면 경우의 수는 항목을 담지 않거나/담는 경우(False - True; 0 - 1)로만 제한되기 때문에 단위 무게 당 가치가 가장 높은 물건이 최적의 답이 아닐 수 있습니다. 이러한 배낭 문제를 0 - 1 배낭 문제(0 - 1 Knapsack Problem)이라고 합니다.

Approach 3. 동적 계획법 (DP)

앞선 두 접근 방식에서, 두 개의 문제점을 찾을 수 있었습니다.

•

너무 느리다.

•

항목을 분할할 수 없을 경우 그리디는 적용할 수 없다.

이를 해결하기 위해 동적 계획법을 사용합니다. 동적 계획법은 이전에 계산된 결과를 저장해 반복적인 계산을 피할 수 있습니다. 또, 현재 시점에서 과거 시점의 최적의 상태를 알 수 있기 때문에 이를 반복하면 최종적인 결과가 최적해임을 보장할 수 있습니다.

먼저 dp[i][w]를 다음과 같이 정의하겠습니다.

dp[i][w] = 1번째 아이템 ~ i번째 아이템과 가방의 용량 w를 사용해 얻을 수 있는 가치의 최대값

즉, 가방의 용량 w가 주어졌을 때, 1번, 2번, 3번, …, i번 아이템 중에서 어떤 아이템들을 담았는지는 모르겠지만 어쨌든 w 용량 내에서 담을 수 있는 최대 가치가 dp[i][w]가 됩니다. 다음으로 i + 1번 아이템에 대해 계산할 때는 이전에 계산된 결과들을 사용하면 됩니다. 용량 w일 때 최대 가치인 dp[i][w]와 w에서 i + 1번 아이템의 무게를 뺐을 때 최대 가치에 i + 1번 아이템의 가치를 더한 값인 dp[i][w - weight[i + 1]] + value[i + 1] 중에서 더 큰 값을 선택하는 것이죠. 수식으로 보면 다음과 같습니다.

dp[i + 1][w] = max(dp[i][w], dp[i][w - weight[i + 1]] + value[i + 1]) (w - weight[i + 1] >= 0)

이 수식이 뜻하는 바를 풀어보면, 다음과 같습니다.

1번째 아이템 ~ i번째 아이템과 가방의 용량 w를 사용해 얻을 수 있는 가치의 최대값에 i + 1번째 아이템이 들어가는 게 더 큰 가치야? 안 들어가는 게 더 큰 가치야?

이렇게 계속해서 업데이트하면 최종적으로 dp[N][W]에서는 1번째 아이템 ~ N번째 아이템과 가방 용량 W를 사용해 얻을 수 있는 가치의 최대값을 얻을 수 있습니다. 단, w - weight[i + 1] < 0일 경우는 아직 i + 1번 아이템을 담을 수 없는 용량의 가방이므로 처리해주어야 합니다.

코드로 보면 다음과 같습니다.

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

/**
 * 평범한 배낭 - DP 풀이
 */
public class Main {
    static int N, K; // 물품의 수 N, 준서가 버틸 수 있는 무게 K
    static int[] W, V; // 각 물건의 무게 W, 가치 V
    static int[][] dp; // dp 배열

    public static void main(String[] args) throws IOException {
        setting();
        solve();
    }

    private static void solve() {
        // 1번째 아이템부터 N번째 아이템까지 돌면서
        for (int i = 1; i <= N; i++) {
            // 무게 1부터 K까지 도는데
            for (int w = 1; w <= K; w++) {
                // 만약 i번째 아이템을 담을 수 있는 용량이라면
                if (w - W[i] >= 0) {
                    // i번째 아이템을 담지 않았을 때 가치가 커? dp[i - 1][w]
                    // i번째 아이템을 담았을 때 가치가 커? dp[i - 1][w - W[i]] + V[i]
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - W[i]] + V[i]);
                } else { // i번째 아이템을 담을 수 없는 가방의 용량이라면
                    dp[i][w] = dp[i - 1][w]; // i - 1번째 아이템을 담았을 때의 정보를 그대로 넣음
                }
            }
        }

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

    private static void setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[N + 1][K + 1]; // 이전 정보를 사용하는 데 편하도록 각각 0번을 패딩

        W = new int[N + 1];
        V = new int[N + 1];

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