• Knapsack 문제
  • 문제 예시. 평범한 배낭
  • 코드
  • 정리

Knapsack 문제

• 여러 물건이 있을때, 특정 조건을 만족하는 조합을 구하는 문제
• Knapsack은 대개 DP를 활용해서 푸는데, 문제 예시를 통해 이해하는 것이 가장 좋다

문제 예시. 평범한 배낭

12865번: 평범한 배낭

N개의 물건이 주어지고, 각 물건은 무게 W와 가치 V를 가지는데, 준서는 최대 K만큼의 무게만 넣을 수 있다.

여기서 준서가 최대한 많은 가치를 담을 수 있는 최대값은? 

예제
4 7 (N K)
6 13 (W V)
4 8
3 6
5 12

• 아주 간단하게 문제를 바라보면, 완전탐색을 통해 모든 조합의 수를 구한다면 문제의 답을 구할 수가 있지만 문제를 조금 잘게 쪼개보면 ‘중복’을 찾을 수 있고 DP를 활용의 최적의 해를 효율적으로 찾아 나갈 수 있다.

• 문제의 해를 점화식으로 표현하면 아래와 같은데,

    dp[i][j] = 처음부터 i번째까지의 물건을 살펴보고, 배낭의 용량이 j였을 때 배낭에 들어간 물건의 가치합의 최대값
  

  • 1부터 N개의 모든 물건들을 살펴보고, 배냥 용량이 K였을 때 이 배낭에 들어가 있는 물건들의 가치합의 최대값이 곧 문제의 해가 된다.
  • 즉 문제의 정답은 dp[N][K] 에 들어가 있을 것이다.
• 그렇다면 dp[i][j]는 어떻게 구할 수 있을까?
  • i번째 물건을 배낭을 넣으려고 할때의 배낭의 용량을 j이다.
    • 이때, i번째 물건의 무게는 w[i]이고, 가치는 v[i]
  • 여기서 용량이 j인 배낭에 i번째 가방을 넣지 않았을 경우 최대값은 dp[i-1][j]이다.
  • 반면에 i번째 가방에 넣었을 경우는 dp[i-1][j-w[i]] + v[i]가 된다
    • i-1번째 까지 물건을 넣었고 j-w[i]였을때 물건을 넣었기 때문에

• 정리하면 점화식의 해는 아래와 같이 구할 수 있게 되는 것이다.

    d[i][j] = Math.max(d[i-1][j], dp[i-1][j-w[i]] + v[i])
  

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NK = br.readLine().split(" ");
        int N = Integer.parseInt(NK[0]);
        int K = Integer.parseInt(NK[1]);
        int[][] dp = new int[N + 1][K + 1];
        int[] W = new int[N + 1];
        int[] V = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            String[] WV = br.readLine().split(" ");
             W[i] = Integer.parseInt(WV[0]);
             V[i] = Integer.parseInt(WV[1]);
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                if (j - W[i] >= 0) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

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

정리

• Knacksack 알고리즘은 특정한 조건을 만족하는 조합을 구할때 사용하는 알고리즘으로 중복된 부분 집합을 저장해놓음으로써 불필요한 연산을 줄이고 성능을 개선하는 것이 핵심이다.
• 즉 하나의 문제를 점화식을 통해 잘게 쪼개 부분 집합의 문제로 쪼개 구하면 되는 문제이다.
• Knacksakc같은 경우 개념적인 이론은 간단하나 크게 와닿지 않는 부분도 있어 다양한 문제에 적용해보면서 푸는 것이 좋은 거 같다

참고

• [알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)