Knapsack Problem
냅색 문제는 해당 문제를 풀기 위한 알고리즘인 냅색 알고리즘과 함께 굉장히 유명하다. 아래 그림과 같이 가방에 넣을 수 있는 무게가 정해져 있고, 각각 무게와 가치가 정해져있는 물건을 가장 최대 가치로 가방에 조합해서 넣는 최상의 조합을 찾는 알고리즘이다.
Knapsack Problem은 물건을 쪼갤 수 있는 Fraction Knaspack Problem과 물건을 쪼갤 수 없는 0-1 KnapSack Problem으로 나뉜다. 이중 0-1 KnapSack Problem을 살펴보려한다.
0-1 Knapsack Problem
가장 기본적으로 생각해볼 수 있는 것은 모든 조합을 고려해보는 것이다. 그러나 크기가 n인 부분집합의 수는 2^n이다.
이번엔 greedy한 기법을 생각해보면 가장 가치있는 물건부터 넣어보는 시도를 해볼 수 있다. 그러나 이러한 방식도 아래와 같은 간단한 예시를 통해서도 최적해가 아님을 알 수 있다.
여기서 좀더 생각을 해서 무게당 가치가 가장 비싼 물건부터 우선적으로 채우는 방법이 있을 수 있다. 이는 나쁘지않은 결과를 가져오지만 매번 최적의 해를 가져올 수는 없다. 아래 예시를 통해 보자.
참고로 Fractional Knapsack Problem에서는 Greedy 알고리즘으로도 최적해를 풀 수 있다.
item 1 + item 3 + item 2 * 1/2 => 30kg 220만원 -> 최적해
DP풀이법
이제 본격적으로 0-1 Knapsack Problem의 최적해를 구하는 DP풀이법을 알아보자.
i > 0 이고 w > 0일 때, 전체 무게가 w가 넘지 않도록 i번째 까지의 항목 중에서 얻어진 최고의 이익(optimal profit)을 P[i][w]라고 하면 아래와 같은 식을 찾을 수 있다.
여기서 P[i-1][w]는 i번째 항목을 포함시키지 않는 경우의 최고 이익이고, pi + P[i- 1][w- wi]는 i번째 항목을 포함시키는 경우의 최고 이익이다.
P[n][W]값은 int P[0..n][0..W]과 같은 2차원 배열을 만든 후, 각 항을 계산하여 채워 넣으면 된다. 여기서 P[0][w] = 0, P[i][0] = 0으로 놓으면 되므로, 계산해야 할 항목의 수는 nW ∈ Θ(nW)가 된다. 여기서 n과 W와는 아무런 상관관계가 없다. 따라서, W = n!이라고 한다면 수행시간은 Θ(n × n!)이 된다. 그렇게 되면 이 알고리즘은 brute force 알고리즘보다도 나을게 하나도 없다. 따라서 이 알고리즘을 최악의 경우에 Θ(2n) 시간에 수행될 수 있도록, 때로는 훨씬 빠르게 수행될 수 있도록 개량해야한다.
착안점은 P[n][W]를 계산하기 위해서 (n-1)번째 행을 모두 계산할 필요가 없다는데 있다. 즉, P[n-1][W]와 P[n-1][W-wn] 두 항만 계산하면 된다. 이런 식으로 n = 1이나 w ≤ 0일때 까지 계속해 나가면 된다.
예로서 위의 예에서 P [3][30]을 계산해 보자. 개량 알고리즘은 다음과 같이 7개 항만 계산하는데 비해서, 이전 알고리즘은 3 × 30 = 90항을 계산해야 한다.
그러면 해당 알고리즘의 최악의 경우 수행시간을 계산해 보자. (n- i )번째 행에서 기껏해야 2^i 항을 계산하므로, 총 계산하는 항 수는 1 + 2 + 2^2 +…+ 2^(n-1) = 2^n - 1이된다. 따라서 Θ (2^n)가 된다. 위의 두 가지 경우를 합하면 최악의 경우의 수행시간은 Ο(minimum(2^n,nW ))이다.
분할정복 방법으로도 이 알고리즘을 설계할 수도 있고, 그 최악의 경우 수행시간은 Θ(2^n)이다. 아직 아무도 이 문제의 최악의 경우 수행시간이 지수(exponential)보다 나은 알고리즘을 발견하지 못했고, 아직 아무도 “그러한 알고리즘은 없다”라고 증명한 사람도 없다. 따라서 Knapsack problem도 NP문제이다.