이 알고리즘의 핵심 아이디어는 그리디(Greedy) 기법이 분할 가능한 배낭(Fractional Knapsack) 문제에서 최적의 해를 보장한다는 사실을 활용하는 것입니다.
특정 노드를 통해 더 나은 해를 얻을 수 있는지 판단하려면, 그 노드를 경유하는 경우에 그리디 기법으로 계산한 이론상 최적해(상한값, Bound)를 구합니다. 만약 그리디 기법으로 계산한 값조차 지금까지 찾은 최적의 해보다 작다면, 해당 노드를 탐색해도 더 나은 결과를 얻을 수 없으므로 가지치기(Pruning)를 할 수 있습니다.
전체 알고리즘
- 단위 무게당 가치(value/weight 비율)를 기준으로 모든 아이템을 내림차순으로 정렬합니다. 이렇게 하면 그리디 기법으로 상한값(Upper Bound)을 계산할 수 있습니다.
- 최대 이익을 초기화합니다. 예: maxProfit = 0
- 빈 큐(Queue) Q를 생성합니다.
- 결정 트리(Decision Tree)의 더미(Dummy) 노드를 생성하여 큐 Q에 삽입(enqueue)합니다. 더미 노드의 이익과 무게는 0입니다.
- 큐 Q가 빌 때까지 다음 과정을 반복합니다.
- 큐에서 하나의 노드를 꺼냅니다. 꺼낸 노드를 u라고 합시다.
- 다음 레벨 노드의 이익(profit)을 계산합니다. 이 이익이 maxProfit보다 크면 maxProfit을 갱신합니다.
- 다음 레벨 노드의 상한값(bound)을 계산합니다. 상한값이 maxProfit보다 크면 다음 레벨 노드를 큐 Q에 추가합니다.
- 다음 레벨 노드를 해(solution)에 포함하지 않는 경우도 고려하여, 레벨만 다음 단계로 넘기고 무게와 이익은 현재 값을 유지하는 노드를 큐에 추가합니다.
예제
입력
// 각 쌍(pair)에서 첫 번째 값은 아이템의 무게,
// 두 번째 값은 아이템의 가치를 의미합니다.
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
출력
The maximum possible profit = 235
위 예제에서 배낭의 용량이 10일 때, 브랜치 앤 바운드 기법을 적용하면 얻을 수 있는 최대 이익은 235입니다. 이처럼 브랜치 앤 바운드는 완전 탐색(Brute Force)에 비해 불필요한 탐색 공간을 효과적으로 줄여주면서 0/1 배낭 문제의 최적해를 구할 수 있습니다.