算法分析与设计实验报告第 7 次实验姓名学号班级时间6.4上午地点四合院 实验名称优先队列式分支限界法求解0-1背包问题实验目的通过上机实验，要求掌握优先队列式分支限界法求解0-1背包问题的问题描述、算法设计思想、程序设计。实验原理1、使用优先队列式分支限界法算法，根据不同的输入用例，能准确的输出背包能装的最大价值，并计算出程序运行所需要的时间。2、分支限界法常以广度优先或最小耗费优先（最大效益优先）方式搜索问题的解空间树， 对于0-1背包问题的解空间树是一个棵子集树。3、在分支限界法中有一个活结点表，活结点表中的每个活结点只有一次机会成为扩展结点，一旦成为 扩展结点就一次性产生所有儿子结点，在这些儿子结点中，导致不可行解或导致非最优解的儿子 结点被舍弃，其余儿子结点被加入到活结点表中。4、为了尽快找到0-1背包问题的解，每次选取下一个活结点成为扩展结点的判断依据是当前情况下 最有可能找到最优解的下一个结点。因此，每次选择扩展结点的方法：当前情况下，在活结点表中 选择活结点的上界，最大的活结点
