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

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

为了检查特定节点是否可以为我们提供更好的解决方案，我们使用贪婪法计算最优解（通过该节点）。如果贪婪法本身计算出的解比迄今为止最好的解还要好，那么我们就无法通过该节点获得更好的解。

完整的算法如下：

  • 根据单位重量的价值比率的递减顺序对所有物品进行排序，以便可以使用贪婪法计算上限。

  • 初始化最大利润，例如 maxProfit = 0

  • 创建一个空的队列 Q。

  • 创建一个决策树的虚拟节点，并将其插入或入队到 Q 中。虚拟节点的利润和重量为 0。

  • 当 Q 不为空时，执行以下操作。

    • 从 Q 中取出一个项目。令提取的项目为 u。

    • 计算下一层节点的利润。如果利润高于 maxProfit，则修改 maxProfit。

    • 计算下一层节点的界限。如果界限高于 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

更新于：2020年1月29日

2K+ 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告