[Algorithm] 배낭문제, 냅색(Knapsack)이란?

Knapsack이란?

냅색(Napsack) 문제는 배낭에 담을 수 있는 무게 한계가 정해져 있고,

각각의 물건들은 무게와 가치가 정해져 있을 때, 배낭에 담을 수 있는 최대 가치의 합을 구하는 문제입니다.

 

배낭문제는 대표적으로 두 가지 종류로 나뉩니다.

1. 0-1 knapsack problem: 각각의 물건은 단 하나씩만 존재하며, 배낭에 담거나 담지 않거나 둘 중 하나의 선택만 가능하다.

2. Fractional knapsack problem: 각각의 물건은 무게에 비례하여 일부분만 담을 수 있으며, 물건을 자를 수 있다.

 

 

Branch and Bound

---

Branch and Bound는 최적화 문제를 풀기 위한 알고리즘으로 가능한 모든 해를 차는 대신,

최적의 해를 빠르게 찾기 위해 탐색 범위를 줄이는 방식으로 작동합니다.

 

 

문제를 풀기 위한 5가지 개념입니다.

① benefit: 가방에 담긴 benefit의 합

② max_benefit: 이전 node와 현재 node의 benefit 값을 비교해서 얻은 benefit의 최대값

③ weight: 가방에 담긴 무게의 합

④ total_weight: 현재 담겨 있는 value의 무게와 앞으로 담길 수 있는 무게의 합

weight는 현재 가방에 담긴 value의 무게이고, 시그마는 total을 넘지 않는 상태까지 넣은 value의 무게입니다.

 

⑤ bound: 가방에 담길 수 있는 최대한의 benefit 값

bound에서 benefit은 이미 넣어진 value들의 benefit이고, 

시그마 b𝙅는 앞으로 잘리지 않고 넣어질 값의 benefit,

W-tot_weight는 잘리지 않고 넣어질 값까지 넣은 무게를 들어갈 수 있는 총 무게에서 뺀 값,

bᴷ/wᴷ는 잘라서 넣을 수 있는 value의 benefit을 weight으로 나눈 값입니다.

 

즉, (W-tot_weight)xbᴷ/wᴷ는 잘라서 넣을 수 있는 benefit을 의미합니다.

 

 

Bound를 통해 노드가 뻗어 나갈지 아니면 멈출지 결정하게 됩니다.

뻗어 나가는 경우를 promising하다하고, 뻗어 나가지 않는 경우를 non-promising 하다고 합니다.

 

promising은 max_benefit보다 bound가 크면서, 현재 가방의 무게가 들어갈 수 있는 무게를 넘지 않았을 때를 가르킵니다.

 

Branch and Bound Problem

---

Which vertex has the maximum benefits?

(total weight: 10)

Benefit	Weight	Benefit(b)/Weight(w)
60	5	12
30	2	15
20	4	5
70	7	10

 

 

문제를 받고 해야할 첫 번재 일은 b/w 값을 내림차순(descending order)으로 정렬하는 일입니다.

Benefit	Weight	Benefit(b)/Weight(w)
30	2	15
60	5	12
70	7	10
20	4	5

 

 

다음으로는 Max_benefit을 두고 노드를 하나씩 그려주는 일입니다.

(노드 안에는 benefit, weight, bound가 들어갑니다.)

 

왼쪽 노드는 value를 집어 넣는 노드, 오른쪽 노드는 value를 집어 넣지 않는 노드라는 것을 명심해야 됩니다.

 

(0, 0) Bound = 0 + 90 + (10-7)/10 = $120

 

max_benefit = 0

이때 w<W이고 (w: 현재 가방에 들어있는 value의 무게<W: 가방에 들어갈 수 있는 value의 최대 무게),

max_benefit ≤ bound 이기 때문에 promissing합니다.

 

이로써 branch를 뻗어 나가면

(1, 1) Benefit(B) = $30 (첫 번째 value의 benefit)

(1, 1) Weight(W) = 2 (첫 번째 value의 weight)

(1, 1) Bound = 30 + 60 (10-7)/10 = $120

 

 

(1, 2) Benefit(B) = $0 

(1, 2) Weight(W) = 0

(1, 2) Bound = 0 + 60 + (10-5)/10 = $110

여기서 알 수 있는 점은 오른쪽 자식 노드의 benefit과 weight는 부모 노드를 따라옵니다.

 

max_benefit = $30 (1, 1)

 

 

두 노드 모두 promising하기 때문에 branch를 뻗어나갈 수 있습니다.

 

(2, 1) Benefit(B) = $30 + $60 = $90 (첫 번째 노드 + 두 번째 노드)

(2, 1) Weight(W) = 2 + 5

(2, 1) Bound = 90 + 0 + (10-7)/10 = $120

 

(2, 2) Benefit(B) = $30 (첫 번째 노드)

(2, 2) Weight(W) = 2

(2, 2) Bound = 30 + 70 + (10-9)/5 = $105

 

(2, 3) Benefit(B) = $60 (두 번째 노드)

(2, 3) Weight(W) = 5

(2, 3) Bound = 60 + 0 + (10-5)/10 = $110

 

(2, 4) Benefit(B) = $0

(2, 4) Weight(W) = 0

(2, 4) Bound = 0 + 70 + (10-7)/5 = $85

 

 

max_benefit = $90 (2, 1)

 

 

(2, 4)은 max_benefit이 bound보다 크기 때문에 non-promising합니다.

그래서 (2, 4)을 제외한 (2, 1), (2, 2), (2, 3)은 branch를 뻗어나갈 수 있습니다.

 

(3, 1)를 계산해보면 weight가 W를 넘어가기 때문에 valid하지 않습니다.

 

(3, 2) Benefit(B) = $30 + $60 = $90

(3, 2) Weight(W) = 2+ 5 = 7

(3, 2) Bound = 90 + 0 + (10-7)/5 = $105

 

(3, 3) Benefit(B) = $30 + $70 = $100

(3, 3) Weight(W) =  2 + 7 = 9

(3, 3) Bound = 100 + 0 + (10-9)/5 = $105

 

(3, 4) Benefit(B) = $30

(3, 4) Weight(W) = 2

(3, 4) Bound = 30 + 20 + 0 = $50

 

(3, 5)도 weight가 W를 넘어가기 때문에 valid하지 않습니다.

 

(3, 6) Benefit(B) = $60

(3, 6) Weight(W) = 5

(3, 6) Bound = 60 + 20 + 0 = $80

 

 

max_benefit = $100 (3, 3)

 

 

max_benefit이 bound보다 작으면서 w가 W보다 작은 노드는 (3, 2), (3, 3)입니다.

(4, 1), (4, 3)은 weight가 W를 넘어가기 때문에 valid하지 않습니다.

 

(4, 2) Benefit(B) = $30 + $60 = $90

(4, 2) Weight(W) = 2 + 5 = 7

(4, 2) Bound = 90 + 0 + 0 = $90

 

(4, 4) Benefit(B) = $30 + $70 = $100

(4, 4) Weight(W) = 2 + 7 = 9

(4, 4) Bound = 100 + 0 + 0 = $100

 

 

max_benefit은 그대로 $100 (3, 3)입니다.

 

 

이로써, Maximum benefit을 가지는 node는 (3, 3)입니다.

 

 

 

◡̈