728x90
해당 포스팅은 [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차원 배열의 행, 열, 원소
- 행: 배낭의 최대 수용 무게 ($w_{ \max }$)
- 열: 배낭에 넣을 물체의 색인 ($i$)
- 원소: 최대 수용 무게가 $p$ 인 배낭에 $a_0, a_1, ..., a_q$, $q + 1$ 개의 물체에 대한 최대 가치 ($e_{p, q}$)
먼저, $w_{ \max } = 0$ 의 경우, 배낭에 넣을 수 없으므로, $e_{0,q} (0 \lt q \le n)$ 의 값은 모두 $0$ 이다.$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}$
또한, 물체 $a_0$ 는 존재하지 않으므로 $e_{p,0} (0 \le p \lt W_{ \max })$ 의 값도 모두 $0$ 으로 채워 넣는다.
이제, $e_{p,q}$ 를 더 자세히 살펴보자.$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}$
우리는 크게 물체 $a_q$ 를 배낭에 넣을 것인지 말 것인지를 고민해야 한다.
$e_{p,q}$ 의 값을 구하기 위해, 먼저 $w_q$와 $p$의 대소관계를 파악할 필요가 있다.
다음의 두 가지 경우가 존재하는데, 이는 물체의 무게가 배낭의 최대 수용 무게를 초과할 수 없기 때문이다.
따라서 조건 $w_q \gt p$ 일 경우, 다음을 만족한다.- 물체 $a_q$ 를 배낭에 넣을 수 없다. ($w_q \gt p$)
- 물체 $a_q$ 를 배낭에 넣을 수 있다. ($w_q \le p$)
$$
한편, 조건 $w_q \le p$ 일 경우 즉, 물체 $a_q$ 를 배낭에 넣을 수 있을 때, $e_{p,q-1}$ 와 $e_{p-w_q,q-1}$ 값을 사용하자.
e_{p,q} = e_{p,q-1}
$$
$p$ 만큼 수용 가능한 배낭에 $a_0$ 부터 $a_{q-1}$ 까지의 물체가 적절히 선택되어 최대 가치 ($e_{p,q-1}$) 를 갖는다. 여기에 새로운 물체 ($a_q$) 를 넣고자 할 때, 두 가지 선택지가 생긴다.
넣지 않을 경우,- 물체 $a_q$ 를 넣지 않는다.
- 물체 $a_q$ 를 넣는다.
$$
배낭의 가치는 이전을 따른다.
e_{p,q} = e_{p,q-1}
$$
하지만 넣을 경우,
$$
배낭의 가치는 현재보다 넣을지 고민하는 물체의 무게 ($w_q$) 만큼 덜 수용 가능한 배낭에 현재와 같은 물체 ($a_0$ 부터 $a_q$ 까지의 물체) 만으로 만들 수 있는 최대 가치 ($e_{p-w_q,q-1}$) 와, 넣을지 고민하는 물체의 가치 ($v_q$) 를 더한 값으로 나타낼 수 있다.
e_{p,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)$ 를 반으로 나눈 후 채워 넣을 수 있기 때문이다.
이러한 사실은 아래 수식의 오류를 불러 일으킨다.
$$
물체를 배낭에 넣을 것인가 와 넣지 않을 것인가 가 아닌 얼마나 넣을 것인가의 질문이 되면서, $w_q \gt p$ 이라고 반드시 $e_{p,q} = e_{p,q-1}$ 이 된다는 보장이 사라진 것이다.
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}
$$
예시를 들어보자.
초기 조건이 다음과 같다고 할 때,
$e_{2,2}$ 와 $e_{2,1}$ 의 값은- $W_{\max} = 4$
- $A = { (1, 2), (2, 3), (3, 5) }$
$$
이므로 반례를 쉽게 찾을 수 있다.
\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)를 만족할까?
그렇다고 하기엔 아직 부족하다.
위 식을 따르면 물체가 제시된 순서대로 배낭에 넣을 수 있는 만큼 꽉꽉 채우게 되는데, 만약 더 높은 효용을 내는 물체가 뒤에 배치되어 차례에 오기 전 배낭이 꽉 차버렸을 때는 최적의 경우와 멀어지기 때문에 그렇다.
이때, 물체의 순서를 적절히 정렬하여 이와 같은 문제를 해결할 수 있다.
두 분수를 비교할 때 통분을 하는 것과 같이, 우리는 두 물체를 비교할 때, 단위 무게당 가치로써 비교할 수 있다.
물체를 분할할 수 있다는 것은 곧, 단위 무게당 가치가 큰 물체가 우선권을 갖는다는 의미이다.
단위 무게당 가치를 표에 추가하면 다음과 같다.
물체의 순서를 단위 무게당 가치의 내림차순으로 정렬한 후에야 비로소 위 점화식이 최적 하위 구조 (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$
또한, 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 배낭 문제에서 효과적으로 사용되고, 분할 배낭 문제에서도 사용할 수 있지만, 사실상 그리디 알고리즘으로 귀결된다.
관련 포스팅
728x90
'Computer Science > Problem' 카테고리의 다른 글
| [Problem] 배낭 문제의 그리디 알고리즘적 접근 (Knapsack, Greedy) (0) | 2023.09.28 |
|---|---|
| [Problem] 배낭 문제의 브루트 포스 알고리즘적 접근 (Knapsack, Brute Force) (0) | 2023.09.28 |
| [Problem] 배낭 문제 (Knapsack Problem) (0) | 2023.09.28 |
