[Problem] 배낭 문제의 브루트 포스 알고리즘적 접근 (Knapsack, Brute Force)

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

• 브루트 포스 배낭 (BFKnapsack) 클래스 구현

class BFKnapsack(Knapsack):
  def get_algorithm(self): return 'Brute Force'
  def zero_one_solve(self):
    # TODO: 0-1 배낭 문제 브루트 포스로 구현

3.1.1. 0-1 배낭 문제

• 접근
  $n$ 개의 물체를 배낭에 넣고자 할 때, 가능한 경우의 수는 집합 $A$의 가능한 부분집합의 개수인 $2^n$ 이고, 이는 곧 시간 복잡도가 $O(2^n)$ 임을 의미한다. 기하급수적 복잡도(Exponential Complexity) 를 지닌 해당 접근은 별로 좋지 못하다고 할 수 있다.

 

• 구현

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

  for i in range(2 ** n):
    sub_items = []      # 부분집합
    sub_total = [0, 0]  # 무게합, 가치합

    for j in range(n):
      # j번째 물건 선택
      if (i >> j) & 1:
        item = self.items[j]
        sub_items.append(item)
        sub_total[0] += item.weight
        sub_total[1] += item.value

    # 용량 초과 여부
    exceeded = sub_total[0] > self.w_max
    # 더욱 가치 있는지 여부
    better = sub_total[1] > m

    if not exceeded and better:
      m = sub_total[1]
      self.best = sub_items

  # 결과 출력
  self.result(frac=False)

3.1.2. 분할 배낭 문제

• 접근
  물체의 분할이 연속적으로 가능할 경우, 하나의 물체를 분할하는 경우의 수부터 무한하기 때문에 브루트 포스는 아예 사용하지 못하게 된다.
  가령, $n$개의 보석을 배낭에 넣는 경우의 수도 $2^n$개나 되는데, 하나의 보석을 얼마큼 포함할지(0~100%)도 연속적이라면, 경우의 수를 파악하는 것이 불가능하다.
  
  백번 양보하여 이산적 분할로 제한하더라도, 0-1 배낭 문제보다 훨씬 많은 경우의 수를 고려해야 한다.
  * 이 포스팅에서는 연속적 분할 배낭 문제만 취급하겠다.

 

• 구현
  구현 불가능

3.1.3. 결론

위와 같은 이유 때문에 배낭 문제의 대한 해결 방법으로 브루트 포스 알고리즘적 접근은 바람직한 접근법이 아니다.

---

관련 포스팅

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