Knapsack 문제

배낭 문제는 DP 알고리즘의 대표적인 문제로 DP를 이해하기에 좋은 예시이다.

주어진 물건들 중에서 일부를 선택해 배낭에 담을 때, 주어진 무게를 넘지 않으면서 얻을수 있는 가장 최대의 가치를 구하는 문제이다.

이 문제를 단순하게만 바라보면 어?? 최대 가치를 구하는 것이니 가치가 제일 큰 물건부터 담는다고 생각하기 쉬운데, 이렇게 구하면 Greedy 전략으로 풀게 되면서 항상 최적해를 보장 할 수 없기에 Greedy 전략이 아닌 DP 전략을 선택해 항상 최적해를 보장해야 한다.

배낭 문제의 적용 예시

https://www.acmicpc.net/problem/12865

• 물건의 갯수, 배낭의 최대 무게
• 각 물건의 무게, 가치
• 각 물건은 최대 한 번만 선택

문제 풀이

단순하게 전체 탐색으로 접근하면 N개의 물건을 담는다 또는 담지 않는다 2가지 선택이 있다.

따라서 시간 복잡도는 O(2^N)이 되어 N이 최대 100이기에 무조건 시간 초과가 발생한다.

따라서 현재 몇 번째 물건을 체크하는지, 남은 배낭 용량이 같다면 얻을 수 있는 최대 가치는 동일하기에 같은 부분 문제가 반복해서 등장한다.
여기에서 DP 문제로 생각을 할 수 있는 것이다.

이전 DP 글에 기록 한 것처럼 DP를 순서대로 풀어보면 다음과 같다.

1. 상태 정의(State)

dp[w] = 지금까지 고려한 물건들로, 배낭 용량이 w일 때 얻을 수 있는 최대 가치

2. 점화식(Transition) 도출

dp[w] = max(dp[w], dp[w - W] + V)

해당 물건을 담지 않는 경우 VS 해당 물건을 담는 경우(배낭 공간 존재하는 경우)

3. 초기값(Base Case) 설정

dp[0] = 0

코드

public class Main {
    public static void main(String[] args) throws Exception {
        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[] dp = new int[K + 1]; // dp[w] = 용량 w에서의 최대 가치

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

            // 0/1 배낭이므로 뒤에서 앞으로 갱신
            for (int w = K; w >= W; w--) {
                dp[w] = Math.max(dp[w], dp[w - W] + V);
            }
        }

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

• 시간 복잡도 : O(N * K)
• 공간 복잡도 : O(K)

Top Down 방식 VS Bottom Up 방식

DP 문제를 풀 때 두 가지 방식이 존재하는데 탑 다운 방식과 바텀 업 방식이다.

• 탑 다운 : 큰 문제 -> 작은 문제로 내려가며 계산하는 방식
  - 재귀 + 메모이제이션을 사용
  
• 바텀 업 : 작은 문제부터 시작해서 그 결과를 이용해 점점 큰 문제의 해를 만들어가는 방식
  - 반복문을 사용

내가 주로 사용하는 방법은 바텀 업 방식이다.

바텀 업 방식이 문제 풀이를 할 때 시간 복잡도 및 공간 복잡도에서 유리하며 안정적이다.
물론 탑 다운 방식이 좀 더 직관적이지만 재귀의 깊이가 깊어지면 오류가 발생할 가능성이 있기에 더 안정적인 반복문을 사용하는 바텀 업 방식을 주로 사용한다.

배낭 문제의 탑 다운 방식 코드

public class Main {

    static int N, K;
    static int[] W, V;
    static int[][] dp; // dp[i][w] = solve(i, w)
    static final int UNVISITED = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        W = new int[N];
        V = new int[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 = new int[N][K + 1];
        for (int i = 0; i < N; i++) {
            for (int w = 0; w <= K; w++) {
                dp[i][w] = UNVISITED;
            }
        }

        System.out.println(solve(0, K));
    }

    static int solve(int i, int cap) {
        if (i == N) return 0;

        if (dp[i][cap] != UNVISITED) return dp[i][cap];

        int best = solve(i + 1, cap);

        if (cap >= W[i]) {
            best = Math.max(best, solve(i + 1, cap - W[i]) + V[i]);
        }

        // 메모이제이션 저장
        dp[i][cap] = best;
        
        return best;
    }
}

코드를 봤을 때 더 직관적으로 이해를 하기 쉬운 것은 탑 다운 방식이다. 하지만 1차원 배열만 사용하던 바텀 업 방식과는 다르게 2차원 배열이 필요하고 이에 따라 시간 복잡도는 O(N K)로 동일하지만, 공간 복잡도가 O(K) -> O(N K)로 늘어난 상황이다.

또한 코드의 길이도 같이 늘어나기에 배낭 문제의 경우 반복문을 사용하는 바텀 업 방식을 더 추천한다.