算法分析与设计实验报告第 7 次实验姓名学号班级时间6.4 上午地点四合院实验名称优先队列式分支限界法求解 0-1 背包问题实验目的通过上机实验，要求掌握优先队列式分支限界法求解 0-1 背包问题的问题描述、算法设计思想、程序设计。实验原理1、使用优先队列式分支限界法算法，根据不同的输入用例，能准确的输出背包能装的最大价值，并计算出程序运行所需要的时间。2、分支限界法常以广度优先或最小耗费优先（最大效益优先）方式搜索问题的解空间树，对于 0-1 背包问题的解空间树是一个棵子集树。3、在分支限界法中有一个活结点表，活结点表中的每个活结点只有一次机会成为扩展结点，一旦成为扩展结点就一次性产生所有儿子结点，在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。4、为了尽快找到 0-1 背包问题的解，每次选取下一个活结点成为扩展结点的判断依据是当前情况下最有可能找到最优解的下一个结点。因此，每次选择扩展结点的方法：当前情况下，在活结点表中选择活结点的上界，最大的活结点成为当前的扩展结点。这一过程一直持续到找到所需的解或活结点表为空时为止。实验步骤1、定义树结点类 bbnode,用于构造子集树，以便计算最优解；定义堆结点类HeapNode，用于定义堆元素类型；定义最大堆类 MaxHeap，用于实现优先队列定义.物品类 Object，用于保存物品编号和物品的单位重量价值；定义解决 0-1 背包问题的主类 Knap。2、设计求解 0-1 背包问题的主函数 Knapsack，在其中对物品以单位价值量排序。3、设计负责求解 0-1 背包问题的最优值和最优解函数 MaxKnapsack 在其中调用计算结点价值上界函数 Bound，向子集树和最大堆中插入结点函数AddLiveNode 和释放最大堆最大结点的函数 DeleteMax，实现优先级队列。4、输入数据到 input.txt 文件中。5、添加计算运行时间的代码，计算不同规模数据的运行时间，并将结果输出到 output 文件中。6、分析时间复杂度：在最坏的情况下所有的节点都入队，最后一个节点才是最优解，这种情况下时间复杂度是指数阶。最好的情况是只装单位价值最大的物品，其余分支都不符合条件被截去这种情况下时间复杂度是常数关键代码〃物品类classObject{friendTypepKnapsack(Typew*,Typep*,Typew,int,int*);public:intoperator<=(Objecta)const{return(d>=a.d);}private:intID;〃物品编号floatd;〃单位重量价值};〃树结点类classbbnode{fr...
