[Algorithm] 0/1 Knapsack problem - branch & bound

Branch & bound는 한국말로 하면 '분기 한정'이라고 할 수 있는데, 

 

분기를 한정시켜서 쓸데 없는 낭비를 줄이는 방법이다.

 

backtracking보다 나은 방법이라고 하는데, 왜냐면 backtracking은 가보고 진행이 안되면 돌아오는데 branch and bound는 최적해를 찾을 가능성 자체가 없으면 가 보지도 않는 느낌이랄까???

 

이게 어떻게 가능한지 한번 살펴보자. 

 

일단 0/1 knapsack problem이 뭔지는 옛날 게시글에서 설명했으니까 패스한다. 

이글을 참조하세요 https://sweetdev.tistory.com/528

 

 

 

이런 물건 4개가 있었고, 내 가방의 weight의 한계는 15였다고 해보자. 

 

 

내가 branch and bound에서 되게 특이하다고 생각했던 점은, 얘는 profit을 weight으로 나눠서 계산한다는거다. profit / weight이 클 수록 좋은 물건이다. 사실 물건은 담냐/안담냐만 있어서 나눠서 계산할줄은 몰랐는데 얘는 그렇게 하더라구...

 

upper bound와 cost 라는 두개의 값을 각 노드마다 사용한다. upper bound는 물건을 쪼개지 않고 사용한거고, cost는 물건을 쪼개서 weight한계까지 꽉꽉 채워준 느낌이다. 영혼까지 끌어모은 느낌... 여기서 기억할건, upper bound로는 노드를 죽일지 말지를 결정하고 cost로는 갈지 말지 방향을 정한다. 

 

cost의 절댓값이 더 큰쪽으로 가고, upperbound가 저장된 값보다 크면 그 노드를 죽여버린다. upperbound가 저장된값보다 작으면 upper를 업데이트 해준다. 

 

일단 전체의 upper을 ♾로 설정한다. 

 

 

그림을 참고하면 쉽게 알 수 있다

-끝-