数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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-01-30
1K+浏览
广告