algorithm - 背包分支和绑定

Question

我有以下数据：

item   weight   value   value/weight
1      5        40      8
2      2        10      5
3      6        30      5
4      1        12      12
5      2        18      9

容量为 10。如何继续计算节点 0 的上限？我正在计算节点 0 的上限，如下所示：

ub = v + [W-w] * [v/w]
ub = 0 + [10] * [8] = 80

或者我是否需要按价值/重量的降序对项目进行排序，分别为 12、9、8、5、5？然后计算上限？或者我做得对，没有排序，计算上限并继续下一项？

在没有排序的方法中，我不会在节点 0 处获得最大上限，我认为是这样。

ub = 0 + [10] * [12] = 120 // if sorted

已经感谢您的帮助。

Answer 1

节点零的上限是分数背包的贪心解。只需取出具有最高价值/重量比的元素并继续插入它，直到没有空间或完全插入它。并重复该过程。