文章/答案/技术大牛

发布

问背包分支和绑定
EN

Stack Overflow用户

提问于 2013-12-11 22:05:06

回答 1查看 2.1K关注 0票数 1

我有以下数据：

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

谢谢你的帮助。

knapsack-problem

branch-and-bound

algorithm

backtracking

回答 1

Stack Overflow用户

发布于 2014-01-22 17:14:09

节点0的上界是分数背包的贪婪解。只需获取具有最高值/权重比的元素，并继续插入它，直到没有空间或完全插入它。然后重复这个过程。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/20521227

复制

相似问题

问背包分支和绑定
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问背包分支和绑定EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问背包分支和绑定
EN