Branch and bound, BFS 0/1 Knapsack

Knapsack 알고리즘이란, 무게(크기)가 한정된 가방이 있고, 넣을 수 있는 물건의 무게(크기)와 가격이 정해져 있을 때 어떤 물건을 버리고 어떤 물건을 넣어야 최대한의 이익을 얻을 수 있는가를 구하는 알고리즘이다.

 

Branch and Bound에 대해서는 TSP에서 설명 했으므로 바로 문제를 풀어보자. 목적에 따라 bound를 구하는 방법만 다를 뿐 다 같은 맥락이다.

 

1. W = 11

i	pi	wi	pi/wi
1	20	2	10
2	21	3	7
3	12	2	6
4	35	7	5

 

input 값는 이런 식으로 주어진다. pi는 물건 i에 대한 profit, wi는 weight, pi/wi는 단위무게당 profit이다. 이 input은 pi/wi이 큰 순서대로 sorting되어 들어오며, sorting되지 않았다면 sorting부터 하고 시작해야 한다.

 

이 문제도 root부터 차례대로 bound값을 구해야 한다.

bound값은, 이 물건들을 쪼갤 수 있다고 가정하고, 쪼갠 물건도 그 단위 비율만큼의 가치가 있다고 가정한다. 이때 pi/wi가 쓰인다. profit이 35이고 weight가 7인 물건을 5만큼만 넣으면 pi/wi * 5 = 25만큼의 profit을 취하는 것이다.

물론 0/1 knapsack에선 이게 허용되지 않는다. '0/1'은 모아니면 도라는 뜻으로, 물건을 넣거나 못넣거나 둘중의 하나이지 쪼개는것은 허용이 안된다는 뜻이다.

그렇기 때문에 단위 무게당 이익이 가장 큰 순서대로 물건을 최대한 쪼개서 넣는 것은 이상적인 케이스이며, 무조건 0/1방식으로 물건을 넣은것 보다는 이익이 클 수 밖에 없다. 이 문제에선 이것을 bound로 잡는다.

 

root node에선 아무 물건도 넣지 않았을때 그냥 최대의 이익을 계산한다.

물건 1, 2, 3을 넣으면 53만큼의 이익이 발생하고 무게는 7이다. 그럼 넣을 수 있는 무게는 4만큼이기 때문에 '물건4'는 쪼개서 넣어야 한다. 단위 무게당 이익이 5인것을 4만큼 넣으면 20의 이익이 증가한다. 즉, 루트 노드에서의 bound는 53 + 20 = 73이 된다.