algorithm - 分支定界法改良背包

Question

所以我遇到的问题如下:有一组 N 类对象，在每个类别中有 M 个对象，每个对象都有指定的值和权重。我们必须从每个类别中挑选一个对象，使得权重 <= 某个给定的容量 W，并且该值是最大的。该任务必须使用分支定界法来解决。我很难理解这种方法在这种情况下应该如何工作。你能给我解释一下吗？

Answer 1

算法应该做什么的简短示例。

假设您有 4 件商品 [(weight, value)]= [(3, 5),(8, 10),(1, 2),(4, 5)]。首先根据权重值对它们进行排序 = [(1, 2),(12, 20),(4, 5),(9, 10)]最大权重为 16。

从第一个项目开始制作一棵树，您可以在其中添加或放置一个项目。在树的每一层计算权重，值(value)和仍然留在三者中的值(value)。如果分支中的 left + value 小于您找到的最大值，则关闭该分支。如果重量超过大声，您也可以关闭一个分支。

下面是它应该如何工作的示意图。

                                       (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

* 分支关闭，因为 value+value left< then maximum value in the tree

**由于权重大于大声权重，分支被关闭。

与蛮力方法相比，此方法的好处是可以减少计算量。通过启动每个权重值最高的项目，您很可能会快速关闭分支并减少计算时间。

希望对你有帮助