[Problem] 배낭 문제의 동적 계획법 알고리즘적 접근 (Knapsack, Dynamic Programming)

해당 포스팅은 [Problem] 배낭 문제 (Knapsack Problem) 의 하위 문서입니다.

• DP 배낭 (DPKnapsack) 클래스 구현

from functools import cmp_to_key
from knapsack import Knapsack

class DPKnapsack(Knapsack):
  def get_algorithm(self): return 'Dynamic Programming'

  def zero_one_solve(self):
    # TODO: 0-1 배낭 문제를 DP로 구현
  def fractional_solve(self):
    # TODO: 분할 배낭 문제를 DP로 구현

3.2.1. 0-1 배낭 문제

• 접근
  동적 계획법의 조건 최적 하위 구조 (Optimal Substructure)를 만족하도록 배낭 문제를 하위 문제로 쪼갤 수 있어야 한다.
  배낭 문제는 $W_{ \max }$ 만큼 수용할 수 있는 배낭에 가치의 합이 최대가 되도록 하는 $A$ 의 부분집합을 찾는 문제로 나타낼 수 있었다.
  최대 무게 $W_{ \max }$ 을 수용 가능한 배낭에 $n$ 개의 물체 중 $a_i$ 물체를 담으면 어떻게 될까?
  배낭 내의 가치가 $v_i$ 이 되고, 앞으로 $W_{ \max } - w_i$ 더 담을 수 있다.
  
  이는 다음과 같이 표현될 수 있다.

  무게 ($W_{ \max } - w_i$) 만큼 수용할 수 있는 배낭에 가치의 합이 최대가 되도록 하는 집합 ($A - { a_i }$) 의 부분집합을 찾는 문제

  배낭 문제는 위와 같은 하위 배낭 문제로 쪼개질 수 있고, 이를 기저상태까지 반복함으로 문제를 해결할 수 있다.
  
  배낭 문제가 하위 문제로 쪼개질 때, 배낭의 최대 수용 무게가 변할 수 있음을 유의하자.
  배낭의 가변적 최대 수용 무게를 앞으로 $w_{ \max }$ 라고 한다.
  
  이제 DP에 쓰일 2차원 배열을 만들어보자. 이 배열은 다음의 행과 열을 갖는다.
  

  2차원 배열의 행, 열, 원소

  1. 행: 배낭의 최대 수용 무게 ($w_{ \max }$)
  2. 열: 배낭에 넣을 물체의 색인 ($i$)
  3. 원소: 최대 수용 무게가 $p$ 인 배낭에 $a_0, a_1, ..., a_q$, $q + 1$ 개의 물체에 대한 최대 가치 ($e_{p, q}$)

  $w_{ \max }$ ╲ $i$	$0$	$1$	$\cdots$	$q$	$\cdots$	$n$
  $0$	$e_{0,0}$	$e_{0,1}$	$\cdots$	$e_{0,q}$	$\cdots$	$e_{0,n-1}$
  $1$	$e_{1,0}$	$e_{1,1}$	$\cdots$	$e_{1,q}$	$\cdots$	$e_{1,n-1}$
  $\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\cdots$	$\vdots$
  $p$	$e_{p,0}$	$e_{p,1}$	$\cdots$	$e_{p,q}$	$\cdots$	$e_{p,n-1}$
  $\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
  $W_{ \max }$	$e_{W_{ \max },0}$	$e_{W_{ \max },1}$	$\cdots$	$e_{W_{ \max },q}$	$\cdots$	$e_{W_{ \max },n-1}$

  먼저, $w_{ \max } = 0$ 의 경우, 배낭에 넣을 수 없으므로, $e_{0,q} (0 \lt q \le n)$ 의 값은 모두 $0$ 이다.
  또한, 물체 $a_0$ 는 존재하지 않으므로 $e_{p,0} (0 \le p \lt W_{ \max })$ 의 값도 모두 $0$ 으로 채워 넣는다.

  $w_{ \max }$ ╲ $i$	$0$	$1$	$\cdots$	$q$	$\cdots$	$n$
  $0$	$0$	$0$	$\cdots$	$0$	$\cdots$	$0$
  $1$	$0$	$e_{1,1}$	$\cdots$	$e_{1,q}$	$\cdots$	$e_{1,n-1}$
  $\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$	$\cdots$	$\vdots$
  $p$	$0$	$e_{p,1}$	$\cdots$	$e_{p,q}$	$\cdots$	$e_{p,n-1}$
  $\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$	$\vdots$
  $W_{ \max }$	$0$	$e_{W_{ \max },1}$	$\cdots$	$e_{W_{ \max },q}$	$\cdots$	$e_{W_{ \max },n-1}$

  이제, $e_{p,q}$ 를 더 자세히 살펴보자.
  
  우리는 크게 물체 $a_q$ 를 배낭에 넣을 것인지 말 것인지를 고민해야 한다.
  $e_{p,q}$ 의 값을 구하기 위해, 먼저 $w_q$와 $p$의 대소관계를 파악할 필요가 있다.
  
  다음의 두 가지 경우가 존재하는데, 이는 물체의 무게가 배낭의 최대 수용 무게를 초과할 수 없기 때문이다.
  

  1. 물체 $a_q$ 를 배낭에 넣을 수 없다. ($w_q \gt p$)
  2. 물체 $a_q$ 를 배낭에 넣을 수 있다. ($w_q \le p$)

  따라서 조건 $w_q \gt p$ 일 경우, 다음을 만족한다.
  

  $$e_{p,q} = e_{p,q-1}$$

  한편, 조건 $w_q \le p$ 일 경우 즉, 물체 $a_q$ 를 배낭에 넣을 수 있을 때, $e_{p,q-1}$ 와 $e_{p-w_q,q-1}$ 값을 사용하자.
  $p$ 만큼 수용 가능한 배낭에 $a_0$ 부터 $a_{q-1}$ 까지의 물체가 적절히 선택되어 최대 가치 ($e_{p,q-1}$) 를 갖는다. 여기에 새로운 물체 ($a_q$) 를 넣고자 할 때, 두 가지 선택지가 생긴다.
  

  1. 물체 $a_q$ 를 넣지 않는다.
  2. 물체 $a_q$ 를 넣는다.

  넣지 않을 경우,
  

  $$e_{p,q} = e_{p,q-1}$$

  배낭의 가치는 이전을 따른다.
  
  하지만 넣을 경우,
  

  $$e_{p,q} = e_{p-w_q,q-1} + v_q$$

  배낭의 가치는 현재보다 넣을지 고민하는 물체의 무게 ($w_q$) 만큼 덜 수용 가능한 배낭에 현재와 같은 물체 ($a_0$ 부터 $a_q$ 까지의 물체) 만으로 만들 수 있는 최대 가치 ($e_{p-w_q,q-1}$) 와, 넣을지 고민하는 물체의 가치 ($v_q$) 를 더한 값으로 나타낼 수 있다.
  $p-w_q$ 의 이유는 물체 $a_q$ 를 넣음으로써 배낭의 최대 수용 무게 $p$ 를 꽉 채우기 위함이다.
  
  따라서 다음을 만족한다.
  

  $$e_{p,q} = \begin{cases} e_{p,q-1} & \text{if} \ w_q \gt p \\ \max(e_{p,q-1}, e_{p-w_q,q-1} + v_q) & \text{if} \ w_q \le p \ \end{cases}$$

• 예시
  상당히 내용이 복잡하기 때문에, 간단한 예시를 확인해보자.

0. 초기 조건

초기 조건은 다음과 같다.

• $W_{ \max } = 6$
• $A = { (1, 2), (2, 4), (3, 3), (4, 5) }$

1. 2차원 배열을 그린다.

$w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
$0$
$1$
$2$
$3$
$4$
$5$
$6$

2. $w_{ \max } = 0$, $i = 0$ 에 해당하는 셀을 $0$으로 채운다.

$w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$
$2$	$0$
$3$	$0$
$4$	$0$
$5$	$0$
$6$	$0$

3. 모든 값을 채운다.

$e_{1,1}$

• $(p,q) = (1, 1)$
  $w_1 = 2 \gt 1$ 이므로 $e_{1,1} = e_{1,0} = 0$
  

  $w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
  $0$	$0$	$0$	$0$	$0$	$0$
  $1$	$0$	$0$
  $2$	$0$
  $3$	$0$
  $4$	$0$
  $5$	$0$
  $6$	$0$

$e_{2,1}$ ~ $e_{6,1}$

• $(p,q) = (2, 1)$
  $w_1 = 2 \le 2$ 이므로 $e_{2, 1} = \max(e_{2, 0}, e_{2-2,0} + v_1) = \max(0, 2) = 2$
  

  $w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
  $0$	$0$	$0$	$0$	$0$	$0$
  $1$	$0$	$0$
  $2$	$0$	$2$
  $3$	$0$
  $4$	$0$
  $5$	$0$
  $6$	$0$

$$\vdots$$

• $(p,q) = (6, 1)$
  $w_1 = 2 \le 6$ 이므로 $e_{6, 1} = \max(e_{6, 0}, e_{6-1,0} + v_1) = \max(0, 2) = 2$
  

  $w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
  $0$	$0$	$0$	$0$	$0$	$0$
  $1$	$0$	$0$
  $2$	$0$	$2$
  $3$	$0$	$2$
  $4$	$0$	$2$
  $5$	$0$	$2$
  $6$	$0$	$2$

$e_{1,2}$ ~ $e_{3,2}$

• $(p,q) = (1, 2)$
  $w_2 = 4 \gt 1$ 이므로 $e_{2,2} = e_{2,1} = 0$
  

  $w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
  $0$	$0$	$0$	$0$	$0$	$0$
  $1$	$0$	$0$	$0$
  $2$	$0$	$2$
  $3$	$0$	$2$
  $4$	$0$	$2$
  $5$	$0$	$2$
  $6$	$0$	$2$

$$\vdots$$

• $(p,q) = (3, 2)$
  $w_2 = 4 \gt 3$ 이므로 $e_{3,2} = e_{3,1} = 2$
  

  $w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
  $0$	$0$	$0$	$0$	$0$	$0$
  $1$	$0$	$0$	$0$
  $2$	$0$	$2$	$2$
  $3$	$0$	$2$	$2$
  $4$	$0$	$2$
  $5$	$0$	$2$
  $6$	$0$	$2$

$e_{4,2}$ ~ $e_{6,2}$

• $(p,q) = (4, 2)$
  $w_2 = 4 \le 4$ 이므로 $e_{4,2} = \max(e_{4,1}, e_{4-2,1} + v_2) = \max(2, 2 + 4) = 6$
  

  $w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
  $0$	$0$	$0$	$0$	$0$	$0$
  $1$	$0$	$0$	$0$
  $2$	$0$	$2$	$2$
  $3$	$0$	$2$	$2$
  $4$	$0$	$2$	$6$
  $5$	$0$	$2$
  $6$	$0$	$2$

$$\vdots$$

• $(p,q) = (6, 2)$
  $w_2 = 4 \le 6$ 이므로 $e_{6,2} = \max(e_{6,1}, e_{6-2,1} + v_2) = \max(2, 2 + 4) = 6$
  

  $w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
  $0$	$0$	$0$	$0$	$0$	$0$
  $1$	$0$	$0$	$0$
  $2$	$0$	$0$	$2$
  $3$	$0$	$2$	$2$
  $4$	$0$	$2$	$6$
  $5$	$0$	$2$	$6$
  $6$	$0$	$2$	$6$

$$\vdots$$

결과

$w_{ \max }$ ╲ $i$	$0$	$1$	$2$	$3$	$4$
$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$0$	$0$	$0$	$0$
$2$	$0$	$2$	$2$	$2$	$2$
$3$	$0$	$2$	$2$	$3$	$3$
$4$	$0$	$2$	$6$	$6$	$6$
$5$	$0$	$2$	$6$	$6$	$6$
$6$	$0$	$2$	$6$	$9$	$9$

따라서 구할 수 있는 최대 가치는 $6$, 물체 조합은 ${ a_1, a_2, a_3 }$ 이다.

• 구현

def zero_one_solve(self):
  n = len(self.items)  # 물체의 개수
  self.best = []       # 최대 가치 조합

  # 2차원 가치 배열
  dp_arr = [[0] * (n + 1) for _ in range(self.w_max + 1)]
  # 물체 포함 여부 판단 배열
  item_arr = [[False] * (n + 1) for _ in range(self.w_max + 1)]

  for q in range(1, n + 1):
    for p in range(1, self.w_max + 1):
      q_w, q_v =  self.items[q - 1].weight, self.items[q - 1].value

      if q_w > p: dp_arr[p][q] = dp_arr[p][q - 1]
      else:
        a, b = dp_arr[p][q - 1], dp_arr[p - q_w][q - 1] + q_v
        dp_arr[p][q] = max(a, b)
        if b > a: item_arr[p][q] = b > a

  # 최적 물체 조합 추적
  p, q = self.w_max, n
  self.sum_w = 0
  while p > 0 and q > 0:
    if item_arr[p][q]:
      self.best.insert(0, (self.items[q - 1], 1.0))
      self.sum_w += self.items[q - 1].weight
      p -= self.items[q - 1].weight
    q -= 1

  self.sum_v = dp_arr[-1][-1]
  self.result(frac=False)

3.2.2. 분할 배낭 문제

• 접근
  
  이제 DP를 사용하여 분할 배낭 문제를 접근해보자.
  0-1 배낭 문제애서는 문제를 다음의 하위 문제로 쪼갤 수 있었다.
  

  • 배낭 문제: 무게 $W_{ \max }$ 만큼 수용할 수 있는 배낭에 가치의 합이 최대가 되도록 하는 집합 $A$ 의 부분집합을 찾는 문제
  • 하위 문제: 무게 ($W_{ \max } - w_i$) 만큼 수용할 수 있는 배낭에 가치의 합이 최대가 되도록 하는 집합 ($A - { a_i }$) 의 부분집합을 찾는 문제

  
  위 방식에 대한 분할 배낭 문제에서의 적합성 판단이 우선되어야 한다.
  분할 배낭 문제에서는 물체의 무게 대비 배낭의 수용 가능 무게가 더 작을 때, 배낭의 남은 공간은 허용되지 않는다.
  가령, 물체 ${ (2, 2), (3, 3) }$에 대해 배낭의 수용 가능 무게가 $4$ 일 경우, 0-1 배낭 문제에서는 물체 $(3, 3)$ 가 포함되고 남은 $1$ 의 공간이 존재했지만, 분할 배낭 문제에서는 이 공간을 물체 $(2, 2)$ 를 반으로 나눈 후 채워 넣을 수 있기 때문이다.
  
  이러한 사실은 아래 수식의 오류를 불러 일으킨다.
  

  $$e_{p,q} = \begin{cases} e_{p,q-1} & \text{if} \ w_q \gt p \\ \max(e_{p,q-1}, e_{p-w_q,q-1} + v_q) & \text{if} \ w_q \le p \ \end{cases}$$

  물체를 배낭에 넣을 것인가 와 넣지 않을 것인가 가 아닌 얼마나 넣을 것인가의 질문이 되면서, $w_q \gt p$ 이라고 반드시 $e_{p,q} = e_{p,q-1}$ 이 된다는 보장이 사라진 것이다.
  
  예시를 들어보자.
  
  초기 조건이 다음과 같다고 할 때,
  

  • $W_{\max} = 4$
  • $A = { (1, 2), (2, 3), (3, 5) }$

  $e_{2,2}$ 와 $e_{2,1}$ 의 값은
  

  $$\begin{cases} e_{2,2} = 2 + 1.5 = 3.5 \\ e_{2,1} = 2 \end{cases}$$

  이므로 반례를 쉽게 찾을 수 있다.
  배낭의 수용 가능 무게가 $0$ 만 아니라면 반드시 어떠한 물체라도 포함될 것이기 때문이다.
  
  따라서 위와 같이 하위 문제로 쪼개는 방식은 적절하지 못하다는 것이 결론이다.
  
  분할 배낭 문제에서는 무조건 다음의 한 개의 선택지만 생각할 수 있다.
  

  배낭에 넣을 수 있는 만큼 물체를 집어넣는다.

  위 문장을 식으로 나타내면 다음과 같다.
  

  $$e_{p,q} = e_{p,q-1} + {v_q \over w_q} \max \left( 0, \ \min \left( w_p, \ p - \sum _{i=1} ^{q-1} w_i \right) \right)$$

  
  위의 점화식은 최적 하위 구조 (Optimal Substructure)를 만족할까?
  
  그렇다고 하기엔 아직 부족하다.
  
  위 식을 따르면 물체가 제시된 순서대로 배낭에 넣을 수 있는 만큼 꽉꽉 채우게 되는데, 만약 더 높은 효용을 내는 물체가 뒤에 배치되어 차례에 오기 전 배낭이 꽉 차버렸을 때는 최적의 경우와 멀어지기 때문에 그렇다.
  
  이때, 물체의 순서를 적절히 정렬하여 이와 같은 문제를 해결할 수 있다.
  두 분수를 비교할 때 통분을 하는 것과 같이, 우리는 두 물체를 비교할 때, 단위 무게당 가치로써 비교할 수 있다.
  
  물체를 분할할 수 있다는 것은 곧, 단위 무게당 가치가 큰 물체가 우선권을 갖는다는 의미이다.
  
  단위 무게당 가치를 표에 추가하면 다음과 같다.
  

  물체 ($a_i$)	$a_1$	$a_2$	$\cdots$	$a_n$
  무게 ($w_i$)	$w_1$	$w_2$	$\cdots$	$w_n$
  가치 ($v_i$)	$v_1$	$v_2$	$\cdots$	$v_n$
  단위 무게당 가치 ($v_i \over w_i$)	$v_1 \over w_1$	$v_2 \over w_2$	$\cdots$	$v_n \over w_n$

  물체의 순서를 단위 무게당 가치의 내림차순으로 정렬한 후에야 비로소 위 점화식이 최적 하위 구조 (Optimal Substructure)를 만족한다.
  
  또한, 2차원으로 생각했던 메모이제이션 또한 1차원만으로 가능해졌다.
  가장 단위 무게당 가치가 높은 물체부터 시작하여 배낭을 꽉 채울 때까지 넣기만 하면 되기 때문이다.
  
  따라서 최종 점화식은 다음과 같다.
  

  $$e_q = e_{q-1} + {v_q \over w_q} \max \left( 0, \ \min \left(w_q, \ W_{ \max } - \sum _{i=1} ^{q-1} w_i \right) \right)$$

  
  복잡하게 적어놓았지만, 결론적으로 후술할 그리디 알고리즘적 접근 방식과 일맥상통한다.
  
  
• 구현

def fractional_solve(self):
  n = len(self.items)  # 물체의 개수 
  self.best = []       # 최대 가치 조합
  self.sum_w = 0

  comp = lambda a, b: b.vpw() - a.vpw()
  sorted_items = sorted(self.items, key=cmp_to_key(comp))

  weights = list(map(lambda item: item.weight, sorted_items))
  dp_arr = [0]

  for i in range(1, n + 1):
    item = sorted_items[i - 1]
    rem_space = max(0, self.w_max - sum(weights[:i - 1]))
    to_put = min(item.weight, rem_space)
    if to_put == 0: break
    self.sum_w += to_put
    self.best.append((item, to_put / item.weight))
    dp_arr.append(dp_arr[-1] + item.vpw() * to_put)

  self.sum_v = dp_arr[-1]

  self.result(frac=True)

3.2.3. 결론

배낭 문제의 대한 해결 방법으로 DP를 사용할 수 있다.
0-1 배낭 문제에서 효과적으로 사용되고, 분할 배낭 문제에서도 사용할 수 있지만, 사실상 그리디 알고리즘으로 귀결된다.

---

관련 포스팅

• 이전 포스팅: [Problem] 배낭 문제의 브루트 포스 알고리즘적 접근 (Knapsack, Brute Force)
• 다음 포스팅: [Problem] 배낭 문제의 그리디 알고리즘적 접근 (Knapsack, Greedy)