算法分析与设计实验报告第五次附加实验姓名学号班级时间12
26上午地点工训楼309实验名称回溯法实验(0-1背包问题)实验目的1
掌握回溯法求解问题的思想2
学会利用其原理求解0-1背包问题实验原理基本思想：0-1背包问题是子集选取问题
0-1背包问题的解空间可以用子集树表示
在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树
当右子树中有可能含有最优解时，才进入右子树搜索
否则，将右子树剪去
基本解题步骤：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
实验步骤（1）首先搜索解空间树，判断是否到达了叶结点；（2）如果左子结点是一个可行节点，就进入左子树；（3）当右子树有可能包含最优解的时候才进入右子树，计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包；（4）利用深度优先搜索整个解空间树，直到将所有的最优解找出位置
关键代码templatevoidKnap::Backtrack(inti){if(i>n)//到达叶子节点{bestp=cp;//更新最优值return;}if(cw+w[i]bestp){Backtrack(i+1);}}测试结果当输入的数据有解时：当输入的数据无解时：当输入的数据稍微大点时：实验分析在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我们只需要验证该程序是否正确即可
0-1背包问题和之前的最优装载其实质上一样的，都是利用解空间树，通过深度优先搜索子集树，通过利用上界函数和一些剪枝策略，从而得到最优解
由于数据较小，所以时间上并不能反映出什么东西
附录：完整代码（回溯法）//0-1
