ImJay

0-1 Knapsack Problem 최고 우선 검색을 사용한 한정분기 (Branch and Bound) 서론 한정 분기 전략의 동기 : 되추적의 비효율되추적의 탐색 과정에서 Valid가 적용되더라도 여전히 상당한 비율의 정점을 방문하지 않아도 됨을 발견 되추적의 비효율 해결책 : 각 노드를 방문할 때마다 한계치(bound)를 계산 한계치(Bound) : 해당 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계 값 0/1 Knapsack Problem의 최고 우선 검색을 사용한 한정분기(Branch and Bound) 전략 1. 그 노드의 profit과 weight를 계산한다. 2. 그 노드의 bound를 계산한다. 3. 현재 노드의 profit이 maxprofit보다 크면 maxpr..