这个想法是为了实现贪婪方法为分数背包问题提供最佳解决方案这一事实。
为了检查特定节点是否可以为我们提供更好的解决方案，我们计算最佳解决方案（通过节点）实施贪心方法。如果贪心法本身计算出的解比目前为止最好的解要多，那么我们就无法通过节点获得更好的解。
完整的算法如下 -
根据每单位重量的价值比率的降序对所有项目进行排序，以便可以使用贪心法计算上限。
立即学习“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 item
Item 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背包问题的详细内容，更多请关注php中文网其它相关文章！
c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！
广告Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
342
收藏
