在 C/C++ 中使用分支定界法解决 0/1 背包问题?
cc++server side programmingprogramming更新于 2024/9/7 5:26:00
这个想法是为了实现贪婪方法为分数背包问题提供最佳解决方案的事实。
为了检查特定节点是否能为我们提供更好的解决方案，我们计算实施贪婪方法的最优解决方案(通过该节点)。如果贪婪算法本身计算出的解大于目前的最佳解，那么我们就无法通过该节点获得更好的解。
完整算法如下 −
按照单位重量价值比的降序对所有项目进行排序，以便可以计算出实施贪婪方法的上限。
初始化最大利润，例如 maxProfit = 0
创建一个空队列 Q。
创建决策树的虚拟节点并将其插入或入队到 Q。虚拟节点的利润和权重为 0。
当 Q 不空缺或为空时执行以下操作。
从 Q 中创建一个项目。让提取的项目成为 u。
计算下一级节点的利润。如果利润高于 maxProfit，则修改 maxProfit。
计算下一级节点的界限。如果界限高于 maxProfit，则将下一级节点添加到 Q。
考虑下一级节点不被视为或不被视为解决方案的一部分的情况，并将一个节点添加到队列中，级别为下一个，但权重和利润不处理或考虑下一级节点。
下面给出说明 −
输入
// 每对中的第一个被视为项目的权重
// 第二个被视为项目的价值
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
输出
The maximum possible profit = 235
