[Problem] 배낭 문제의 그리디 알고리즘적 접근 (Knapsack, Greedy)

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

• 그리디 배낭 (GreedyKnapsack) 클래스 구현

class GreedyKnapsack(Knapsack):
    def get_algorithm(self): return 'Greedy'
  
    def fractional_solve(self):
      # TODO: 분할 배낭 문제를 그리디로 구현

3.3.1. 0-1 배낭 문제

• 접근
  0-1 배낭 문제를 그리디 알고리즘적으로 접근할 수 있을까?
  
  DP에서 사용한 단위 무게당 가치의 개념을 다시 사용해보자.
  물체를 단위 무게당 가치 내림차순으로 정렬한 다음 배낭에 넣을 수 있는 만큼 차례로 넣는다면 반드시 최고 가치를 가질 수 있을까?
  
  그렇지 않다.
  
  안타깝게도 단위 무게당 가치에 따른 물체의 선택이 항상 최적의 해를 보장하지 못한다.
  
  집합 $A$ 를 단위 무게당 가치 내림차순으로 정렬하였다고 생각하자.
  ${v_{i-1} \over w_{i-1}} \gt {v_i \over w_i}$ 이라고 꼭 $w_{i-1} $와 $w_i$, $v_{i-1}$ 와 $v_i$ 의 대소가 결정되지는 않는다는 점을 눈여겨볼 필요가 있다.
  
  
  $v_{i-1} \lt v_i$ 일 때,
  $$ W_{ \max } - \sum _{k = 1} ^{i - 1} w_k \lt w_i \lt w_{i - 1} \lt W_{ \max } - \sum _{k = 1} ^{i - 2} w_k $$
  
  를 만족하는 경우가 반례가 된다.
  
  $$ W_{ \max } -\sum w_k $$
  위 식은 배낭의 남은 공간으로 물체의 무게가 이것보다 작다면 물체를 넣을 수 있고, 크다면 넣지 못한다.
  
  따라서 위 식은 물체 $a_{i-1}$ 가 먼저 배낭에 포함 되지만, 이 때문에 더 높은 가치를 갖는 $a_i$ 가 배낭에 포함되지 못하는 경우를 나타낸다.
  
  예를 들어, 초기 조건이 다음과 같을 때,
  
  $W_{ \max } = 10$
  

  물체 ($a_i$)	$a_1$	$a_2$
  무게 ($w_i$)	$4$	$10$
  가치 ($v_i$)	$10$	$20$
  단위 무게당 가치 ($v_i \over w_i$)	$2.5$	$2$

  그리디 알고리즘으로 구한 해는 물체 $a_1$ 를 선택한 $10$ 이지만, 실제 최적의 해는 물체 $a_2$ 를 선택한 가치 $20$ 의 배낭이다.
  
  따라서 그리디 알고리즘은 0-1 배낭 문제의 해결책을 제시하지 못한다.
  


• 구현
  구현 불가능

3.3.2. 분할 배낭 문제

• 접근
  하지만 물체가 분할될 수 있다면 그리디 알고리즘을 사용할 수 있다.
  
  0-1 배낭 문제에서 더 낮은 가치의 앞선 물체가 먼저 포함될 경우, 최적이 될 수 없는 반례가 존재하였지만, 분할 배낭 문제에서는 그렇지 않다. 남은 공간이 현재 물체의 무게보다 더 클 경우 0-1 배낭 문제에서는 넣지 못했지만 분할 배낭 문제에는 물체를 분할하여 일부를 배낭에 넣을 수 있기 때문이다.
  
  따라서 항상 단위 무게당 가치가 높은 순서대로 물체를 배낭에 포함시키는 것이 결국 최적해를 갖는다.
  이는 이전 포스팅의 분할 배낭 문제의 DP 알고리즘적 접근에서 이야기한 내용과 사실상 같다.
  
  남은 공간에 대하여
  $$ W_{ \max } -\sum w_k $$
  처럼 나타내지 않고, 변수 (rem_space) 를 활용하면 더 쉬운 형태의 구현이 가능하다.
  


• 구현

def fractional_solve(self):
  # 단위 무게당 가치가 높은 순서대로 정렬
  comp = lambda a, b: b.vpw() - a.vpw()
  sorted_items = sorted(self.items, key=cmp_to_key(comp))

  self.best = []
  self.sum_w = 0
  self.sum_v = 0

  for item in sorted_items:
    # 남은 공간
    rem_space = self.w_max - self.sum_w

    # 남은 공간이 현재 아이템의 무게보다 작거나 같으면 물체 일부를 취함
    if rem_space <= item.weight:
      percent = rem_space / item.weight
      self.sum_v += item.vpw() * rem_space
      self.sum_w += rem_space
      self.best.append((item, percent))
      break
    
    # 아이템을 모두 취함
    else:
      self.sum_v += item.value
      self.sum_w += item.weight
      self.best.append((item, 1.0))

  self.result(frac=True)

3.3.3. 결론

그리디 알고리즘을 활용하여 0-1 배낭 문제는 해결할 수 없고, 분할 배낭 문제만 해결 가능하다.

---

관련 포스팅

• 이전 포스팅: [Problem] 배낭 문제의 동적 계획법 알고리즘적 접근 (Knapsack, Dynamic Programming)