使用分支限界法在C/C++中实现0/1背包问题

这个想法是为了实现贪婪方法为分数背包问题提供最佳解决方案这一事实。

为了检查特定节点是否可以为我们提供更好的解决方案，我们计算最佳解决方案（通过节点）实施贪心方法。如果贪心法本身计算出的解比目前为止最好的解要多，那么我们就无法通过节点获得更好的解。

完整的算法如下 -

• 根据每单位重量的价值比率的降序对所有项目进行排序，以便可以使用贪心法计算上限。

• 初始化最大利润，例如 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中文网其他相关文章！