这个想法是为了实现贪婪方法为分数背包问题提供最佳解决方案这一事实。
为了检查特定节点是否可以为我们提供更好的解决方案，我们计算最佳解决方案（通过节点）实施贪心方法。如果贪心法本身计算出的解比目前为止最好的解要多，那么我们就无法通过节点获得更好的解。
完整的算法如下 –
根据每单位重量的价值比率的降序对所有项目进行排序，以便可以使用贪心法计算上限。
立即学习“C++免费学习笔记（深入）”；
初始化最大利润，例如 maxProfit = 0
创建一个空队列 Q。
决策虚拟节点创建树并将其插入或排队到 Q。虚拟节点的利润和权重为 0。
当 Q 不空或为空时执行以下操作。
创建了 Q 中的项目。设提取项为u。
计算下一级节点的利润。如果利润高于maxProfit，则修改maxProfit。
计算下一级节点的界限。如果bound高于maxProfit，则将下一级节点添加到Q。
考虑下一级节点不被视为或考虑为解决方案的一部分的情况，并将节点添加到队列的级别为下一级，但权重和利润不处理或考虑下一级节点。
下面给出的插图 –
输入
// First thing in every pair is treated as weight of item// and second thing is treated as value of itemItem arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};Knapsack Capacity W1 = 10
输出
The maximum possible profit = 235
以上就是使用分支限界法在C/C++中实现0/1背包问题的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444382.html
微信扫一扫 
支付宝扫一扫 
