分支界限算法【0-1背包问题】按照优先队列式（LC）分支限界法求解0-1背包问题， 并给出限界函数，并画出该实例的状态空间树。
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了分支界限算法【0-1背包问题】按照优先队列式（LC）分支限界法求解0-1背包问题， 并给出限界函数，并画出该实例的状态空间树。，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1238字，纯文字阅读大概需要2分钟。
内容图文
目 录
0-1背包问题基本概念（课件）
解决思路：采用优先队列式分支限界
Ø 确定 目标函数上、下界； Ø 确定 目标函数的计算方法；一般情况下，假设当前已对前i个物品进行了某种特定的选择，且背包中已装入物品的重量是w，获得的价值是v，计算该结点的目标函数上界的一个简单方法是，将背包中剩余容量全部装入第i+1个物品，并可以将背包装满，于是，得到限界函数：
Ø 依 上计算从 根结点到叶子结点的目标函数值 直到 表 PT （待处理活结点列表）中 取得极大值 。
分支限界法求解0/1背包问题算法用伪代码描述如下：
算法7.1：分枝限界法求解0/1背包问题
输入：n个物品的重量w[n]，价值v[n]，背包容量W
输出：背包获得的最大价值和装入背包的物品
1. 根据限界函数计算目标函数的上界up；采用贪心法得到下界down；
2. 计算根结点的目标函数值并加入待处理结点表PT；
3. 循环直到某个叶子结点的目标函数值在表PT中取极大值
3.1 i = 表PT中具有最大值的结点；
3.2 对结点i的每个孩子结点x执行下列操作：
3.2.1 如果结点x不满足约束条件，则丢弃该结点；
3.2.2 否则，估算结点x的目标函数值lb，
将结点x加入表PT中；
4. 将叶子结点对应的最优值输出，回溯求得最优解的各个分量。
作业题（期末考试必考）
按照优先队列式（LC）分支限界法求解0-1背包问题， 并给出限界函数，并画出该实例的状态空间树。
老师讲解此题的板书：
博主课堂笔记（仅供参考）：
内容总结
以上是互联网集市为您收集整理的分支界限算法【0-1背包问题】按照优先队列式（LC）分支限界法求解0-1背包问题， 并给出限界函数，并画出该实例的状态空间树。全部内容，希望文章能够帮你解决分支界限算法【0-1背包问题】按照优先队列式（LC）分支限界法求解0-1背包问题， 并给出限界函数，并画出该实例的状态空间树。所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。