0-1 Knapsack

이번에는 0-1 Knapsack 문제에 대해 알아보려고 한다.

(https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/)

일반적으로 해당 문제는 N개의 아이템에 대한 Value와 Weight가 주어졌을 때, 배낭(knapsack)의 최대 허용치 Weight 만큼 아이템을 넣어 최대 Value를 찾는 것이다.

즉, 각각의 아이템을 선택할 필요가 없으며 넣었다 뺐다 (0-1 속성) 하면서 최대 Value를 뽑아내는 것이다.

위의 예시를 보면, Knapsack의 최대인 W = 50 안에서 여러 아이템을 섞는다. (결과는 220)

물론 직관적으로 가장 쉬운 방법은 모든 아이템을 찾아서 일일이 만들어 보는 방법이다. 

def knapSack(W , wt , val , n):         # Base Case      if n == 0 or W == 0 :          return 0        # If weight of the nth item is more than Knapsack of capacity      # W, then this item cannot be included in the optimal solution      if (wt[n-1] > W):          return knapSack(W , wt , val , n-1)         # return the maximum of two cases:      # (1) nth item included      # (2) not included      else:          return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),                     knapSack(W , wt , val , n-1))

이와 관련된 코드를 확인해보자.

먼저 knapSack의 매개 변수는 각각 "W = 허용할 수 있는 최대 Weight, wt = 아이템의 Weight 배열, val = 아이템의 Value 배열, n = 아이템의 전체 길이" 이다.

내부 코드를 보면 단순하게 보일 수 있는데 2가지 경우를 고려한 것이다.

1) n-1 번째의 Weight 값이, 현재 남아있는 배낭의 Weight 보다 큰 경우

2) n-1 번째의 아이템을 사용할 경우와 그렇지 않을 경우 (0-1 속성)

그런데 코드를 보면 눈치 챌 수 있듯이, 모든 아이템을 훑어본다. (Tree 구조 상으로 가정한다면 최대한 많은 Leaf Node를 방문하려고 한다.)

때문에 시간 복잡도는 O(2^n) 된다. (아래 그림 참조)

In the following recursion tree, K() refers to knapSack().  The two 
parameters indicated in the following recursion tree are n and W.  
The recursion tree is for following sample inputs.
wt[] = {1, 1, 1}, W = 2, val[] = {10, 20, 30}

                       K(3, 2)         ---------> K(n, W)
                   /            \ 
                 /                \               
            K(2,2)                  K(2,1)
          /       \                  /    \ 
        /           \              /        \
       K(1,2)      K(1,1)        K(1,1)     K(1,0)
       /  \         /   \          /   \
     /      \     /       \      /       \
K(0,2)  K(0,1)  K(0,1)  K(0,0)  K(0,1)   K(0,0)

위의 그림을 살펴보면, 한 가지 눈에 들어오는 부분이 있을 것이다. 바로 중복되는 계산이다. 

그러므로 중복되는 계산을 Caching 한다면 기존 시간 복잡도인 O(2^n)보다 확실히 많이 줄일 수 있다. (DP 적용)

아래 코드를 통해 최적화된 부분을 확인하도록 하자.

// Returns the maximum value that can be put in a knapsack of capacity W  int knapSack(int W, int wt[], int val[], int n)  {     int i, w;     int K[n+1][W+1];        // Build table K[][] in bottom up manner     for (i = 0; i <= n; i++)     {         for (w = 0; w <= W; w++)         {             if (i==0 || w==0)                 K[i][w] = 0;             else if (wt[i-1] <= w)                   K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);             else                  K[i][w] = K[i-1][w];         }     }        return K[n][W];  }

2차원 배열을 위한 추가 메모리를 사용하여 중복되는 계산을 줄인 코드이다. 특히 위 코드는 DP의 Bottom-Up 방식을 사용하여 K[i][w]의 값을 채워가는 방식이다.

때문에 시간 복잡도는 O(nW)로 줄일 수 있다. 

다만, 고려해야 봐야 할 부분은 DP의 배열 크기이다. n 또는 W의 크기가 커지면 커질 수록 공간 복잡도는 계속 커질 수 밖에 없다.