实验十六：0-1 背包问题（分支限界法）报告
2017061111 李静娴
1．问题描述
给定 种物品和一背包。物品 的重量是 ，其价值为 ，背包的容量为 。问应如何选
择装入背包的物品，使得装入背包中物品的总价值最大
2．实验目的
（1）熟悉分支限界法，并学以致用
（2）熟练掌握 0-1 背包问题算法
3．实验原理
首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在
优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值
的物品装满剩余容量的价值和。
算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，
则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，
仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时
为问题的最优值。
算法的时间复杂度：‰。
4．实验设计
（）
输入数据格式：宏定义集装箱个数 ，背包容量以及物品质量和价值由用户自定义
生成方式：用户输入
数据规模：宏定义设定。
（）
该程序先是设定好物品个数，然后由用户设定背包容量以及物品的质量和价值。再调
用 Knapsack(p, w, c, n)函数输出背包能装下的最大价值。bestx[i]输出最优解。
（）
程序运行的结果有四部分，先是输出背包容量，再输出物品重量和价值，然后输出背
包能装的最大价值，最后输出最优解。
5．实验结果与分析
剩余11页未读，继续阅读
评论0