所以我遇到的问题如下:有一组 N 类对象，在每个类别中有 M 个对象，每个对象都有指定的值和权重。我们必须从每个类别中挑选一个对象，使得权重 <= 某个给定的容量 W，并且该值是最大的。该任务必须使用分支定界法来解决。我很难理解这种方法在这种情况下应该如何工作。你能给我解释一下吗？
最佳答案
算法应该做什么的简短示例。
假设您有 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
**
由于权重大于大声权重，分支被关闭。
与蛮力方法相比，此方法的好处是可以减少计算量。通过启动每个权重值最高的项目，您很可能会快速关闭分支并减少计算时间。
希望对你有帮助
关于algorithm - 分支定界法改良背包，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47135699/