본문 바로가기
IT 이론/자료구조&알고리즘

Branch and bound, BFS 0/1 Knapsack

by 아이들링 2013. 6. 6.

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이 된다.

댓글1

  • 뭐긴뭐야 2019.12.07 03:21

    다른 블로그들 다 똑같은 내용 포스팅해서 이해가 안 됐는데 여기는 이해할 수 있게끔 설명해놨네요. 감사합니다.
    답글