분기 및 바운드 방식을 사용하는 수정 된 배낭

Question

그래서 문제는 다음과 같습니다. 개체의 N 범주 집합이 있으며 각 범주에는 지정된 값과 가중치를 가진 M 개체가 있습니다. 각 카테고리에서 하나의 객체를 선택하여 가중치가 < = 주어진 용량 W이고 값이 최대가되도록해야합니다. 작업은 branch 및 bounds 메서드를 사용하여 해결해야합니다. 나는이 방법이이 상황에서 어떻게 작동해야하는지 이해하기 위해 애 쓰고있다. 설명해 주시겠습니까?

Answer 1

알고리즘이 수행해야하는 간단한 예제.

4 개의 아이템이 있다고 가정하십시오. [(weight, value)]= [(3, 5),(8, 10),(1, 2),(4, 5)]. 무게 = [(1, 2),(12, 20),(4, 5),(9, 10)] 최대 중량 당이 값에 첫 번째 종류의 그 첫 번째 항목에서 시작하여 16

은 나무 당신 광고 중 하나를 만들거나 항목을 삭제할 수 있습니다. 트리의 각 레벨에서 가중치, 값 및 값을 계산합니다.이 값은 여전히 ​​3에 남아 있습니다. 분기의 왼쪽 + 값이 발견 된 최대 값보다 작 으면 해당 분기를 닫습니다. 또한 체중이 소리내어 이상인 경우 지점을 닫습니다.

아래의 그림은 어떻게 작동해야 하는지를 나타낸 것입니다.

         (value)   (0) 
             (weight)  (0) 
             (value left) (37) 
               add   drop 
    (1,2)         <-------  ------>  
            (2)         (0) 
            (1)         (0) 
            (35)         (35) 
    (20,12)   --------------------------------------------------------------- 
         (22)     (2)    (20)    (0) 
         (13)     (1)    (12)    (0) 
         (15)     *(15)    (15)    *(15) 
    (4,5)  ----------------------------------------------------------------------- 
        (27)  (22)       (25)   (20) 
        (17)  (13)       (16)   (12) 
       **(10)  (10)       (10)   (10) 
    (9,10)  --------------------------------------------------------------------------- 
          (31) (20)     (35) (25) (30) (20) 
          (22) (13)     (25) (16) (21) (12) 
          **(0) (0)     **(0) (0) **(0) (0) 
                   win 

* 분기 인해 값 + 값은 트리에서 < 다음 최대 값을 남긴

** 분기 인해 중량이 크게 중량 이상이라고 폐쇄되는 폐쇄된다.

이 방법의 장점은 무차별 방식에 비해 계산을 줄이는 것입니다. 가중치가 가장 높은 항목을 시작하면 분기를 신속하게 종료하고 계산 시간을 줄일 수 있습니다.

잘하면