[Problem] 배낭 문제 (Knapsack Problem)

1. 개요

배낭 문제 (Knapsack Problem)는 최대 수용 무게가 있는 어떤 배낭에 각각의 특정 가치를 갖는 여러 물체를 넣되, 배낭이 지니는 가치가 최대가 되도록 하는 물체의 조합을 찾는 문제를 의미한다.

기본적으로 다음을 정의하면,

배낭의 최대 수용무게: $W_{ \max }$
물체의 집합: $A = \{ a_i | 0 \lt i \le n \}$
물체의 개수: $n$
$i$ 번째 물체의 무게: $w_i$
$i$ 번째 물체의 가치: $v_i$
물체: $a_i = (w_i, v_i)$

물체 ($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$

$W_{ \max }$ 만큼 수용할 수 있는 배낭에 가치의 합이 최대가 되도록 하는 $A$ 의 부분집합을 찾는 문제로 나타낼 수 있다.

주로 도둑이 여러 보석을 한정된 가방 담아 훔쳐 달아나고자 할 때, 가장 큰 이득을 챙길 수 있는 방법으로 널리 알려져 있다.

2. 종류

배낭 문제는 특정 조건에 따라 다음의 두 가지의 종류로 구분된다.

배낭 문제 종류

1. 0-1 Knapsack Problem (0-1 배낭 문제)
2. Fractional Knapsack Problem (분할 배낭 문제)

2.1. 0-1 Knapsack Problem (0-1 배낭 문제)

• 배낭에 넣을 수 있는 물체를 분할할 수 없다는 조건이 포함된다.
같은 예시로, 도둑이 가치 $V$, 무게 $W$를 갖는 보석이 더 이상 분할될 수 없고, 이를 배낭에 넣을 때, 반드시 넣거나 넣지 않는 두 가지 선택지만 존재하는 경우이다.

2.2. Fractional Knapsack Problem (분할 배낭 문제)

• 배낭에 넣을 수 있는 물체를 분할할 수 있다는 조건이 포함된다.
가령 위의 예시에서, 도둑이 가치 $V$, 무게 $W$를 갖는 보석이 가루형태로 존재하여 이를 배낭에 넣을 때, $w(<W)$ 무게 만큼만 분할 수용이 가능한 경우이며 이때의 가치는 $V \times {w \over W}$ 라고 할 수 있다.

3. 접근

배낭 문제는 다음의 알고리즘으로 해결할 수 있다.

0-1	Fractional
브루트 포스, 동적 계획법	(동적 계획법), 그리디

구현

• 물체 (Item) 클래스 구현

class Item:
  # 생성자
  def __init__(self, weight, value):
    self.weight = weight
    self.value = value

  # 단위 무게당 가치
  def vpw(self): return self.value / self.weight

  # 무작위 속성 지정
  @classmethod
  def random(cls):
    w = random.randrange(50, 100)
    v = random.randrange(10, 100)
    return cls(w, v)

  # 출력 문자열 반환
  def to_string(self):
    return '(' + str(self.weight) + ', ' + str(self.value) + ')'

• 배낭 (Knapsack) 클래스 구현

class Knapsack:
  # 생성자
  def __init__(self, w_max, items):
    self.w_max = w_max
    self.items = items

  # 정적 메소드: 무작위 속성 설정
  @classmethod
  def random(cls):
    w_max = 300
    random_items = [Item.random() for _ in range(30)]
    return cls(w_max, random_items)

  # 정적 메소드: 속성 복사
  @classmethod
  def copy_from(cls, k):
    return cls(k.w_max, k.items)

  # 현재 속성값 출력
  def visualize(self):
    print('#### Knapsack ####')
    print('Capacity:', self.w_max)
    item_string = ', '.join(map(lambda item: item.to_string(), self.items))
    print('Items: [', item_string, ']')
    print()

  # 결과값 출력
  def result(self, frac):
    print('####', self.get_algorithm(), 'Result ####')
    print('Type:', 'Fractional' if frac else '0-1', 'Knapsack')
    print()
    print('Best Items: [', ', '.join(map(lambda t: t[0].to_string() + ': ' + str(round(t[1], 1)), self.best)), ']')
    print('Sum of Weights:', self.sum_w)
    print('Sum of Values:', self.sum_v)
    print()

  # 추상 메소드: 알고리즘 종류
  @abstractmethod
  def get_algorithm(self): pass

  # 추상 메소드: 알고리즘에 따라 다르게 구현
  # 0-1 배낭 문제 구현
  @abstractmethod
  def zero_one_solve(self): pass
  # 분할 배낭 문제 구현
  @abstractmethod
  def fractional_solve(self): pass

• 사전 설정
  예시에 사용할 $W_{ \max }$, $A$ 를 미리 설정 (무작위로 설정)

problem = Knapsack.random()
problem.visualize()

#### Knapsack ####
Capacity: 300
Items: [ (92, 85), (84, 71), (93, 20), (59, 43), (59, 28), (58, 10), (53, 50), (61, 39), (66, 48), (97, 42), (95, 54), (65, 21), (83, 68), (80, 39), (68, 57), (68, 93), (99, 27), (83, 94), (75, 98), (78, 18), (97, 60), (91, 63), (93, 25), (52, 53), (99, 57), (90, 76), (57, 26), (88, 22), (79, 94), (97, 31) ]

3.1. 브루트 포스 알고리즘적 접근

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

3.2. 동적 계획법 알고리즘적 접근

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

3.3. 그리디 알고리즘적 접근

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

4. 성능 비교

코드

bf = BFKnapsack.copy_from(problem)
dp = DPKnapsack.copy_from(problem)
gd = GDKnapsack.copy_from(problem)

s = time.time()
bf.zero_one_solve()
e = time.time()

print('Taken Time:', '%.6f' % (e - s), 's')
print()

s = time.time()
dp.zero_one_solve()
e = time.time()

print('Taken Time:', '%.6f' % (e - s), 's')
print()

s = time.time()
dp.fractional_solve()
e = time.time()

print('Taken Time:', '%.6f' % (e - s), 's')
print()

s = time.time()
gd.fractional_solve()
e = time.time()

print('Taken Time:', '%.6f' % (e - s), 's')
print()

출력

#### Brute Force Result ####
Type: 0-1 Knapsack

Best Items: [ (68, 57): 1.0, (68, 93): 1.0, (83, 94): 1.0, (75, 98): 1.0 ]
Sum of Weights: 294
Sum of Values: 342

Taken Time: 4202.699331 s

#### Dynamic Programming Result ####
Type: 0-1 Knapsack

Best Items: [ (68, 57): 1.0, (68, 93): 1.0, (83, 94): 1.0, (75, 98): 1.0 ]
Sum of Weights: 294
Sum of Values: 342

Taken Time: 0.002960 s

#### Dynamic Programming Result ####
Type: Fractional Knapsack

Best Items: [ (68, 93): 1.0, (75, 98): 1.0, (79, 94): 1.0, (83, 94): 0.9 ]
Sum of Weights: 300
Sum of Values: 373.3373493975904

Taken Time: 0.000092 s

#### Greedy Result ####
Type: Fractional Knapsack

Best Items: [ (68, 93): 1.0, (75, 98): 1.0, (79, 94): 1.0, (83, 94): 0.9 ]
Sum of Weights: 300
Sum of Values: 373.3373493975904

Taken Time: 0.000061 s

	0-1	Fractional
브루트 포스	4202.699331 s	-
DP	0.002960 s	0.000092 s
그리디	-	0.000055 s

5. 제출 코드

• Github

---

관련 포스팅

• [Algorithm] 완전 탐색, 브루트 포스 (Brute Force)
• [Algorithm] 동적 계획법 (Dynamic Programming)
• [Algorithm] 그리디, 탐욕 (Greedy)

참고 자료

• [알고리즘 정리] 배낭 문제(Knapsack Problem)