《回溯法实验(0》由会员分享，可在线阅读，更多相关《回溯法实验(0（13页珍藏版）》请在金锄头文库上搜索。
1、回 溯 法 实 验 （ 0- 1 背 包问题）算法分析与设计实验报告第丄次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称回溯法实验(0-1背包问题)实验目的1. 掌握回溯法求解问题的思想2. 学会利用其原理求解0-1背包问题实验原理基本思想：0-1背包冋题是子集选取冋题。0-1背包冋题的解空间可以用子集树 表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜 索就进入左子树。当右子树中有可能含有最优解时，才进入右子树 搜索。否则，将右子树剪去。基本解题步骤：(1) 针对所给问题，定义问题的解空间；(2) 确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用
2、剪枝函数避免 无效搜索。实验步骤(1) 首先搜索解空间树，判断是否到达了叶结点；(2) 如果左子结点是一个可行节点，就进入左子树；(3) 当右子树有可能包含最优解的时候才进入右子树，计算右子 树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依 次装入物品，直至装不下时，再装入物品一部分而装满背包；(4) 利用深度优先搜索整个解空间树，直到将所有的最优解找出 位置。关键代码template vclass Typew, class Typep void Knap:Backtrack( int i) if (in)/到达叶子节点bestp = cp;/更新最优值return ;if (cw
3、+ wi bestp)Backtrack(i+1);当输入的数据有解时:测试结果当输入的数据无解时:当输入的数据稍微大点时:四回溯法Xfufo OReDebuqzeno cnejext阀品上数为：M实验分析巔I軌鬻123EC70?1O牧品价值分别为：12345678? 10妆品重量和忙值分别为； OSJ C9,9) 在实验中并没有生成多组数据，进行比较，也没有利用随机生 成函数，因为在这种有实际有关联的问题中，利用随机生成函数生 成的数据是十分的不合适的，在此我们只需要验证该程序是否正确 即可。0-1背包问题和之前的最优装载其实质上一样的，都是利用 解空间树，通过深度优先搜索子集树，通过利用上
4、界函数和一些剪 枝策略，从而得到最优解。由于数据较小，所以时间上并不能反映 出什么东西。实验心得在这一章的回溯算法中，我们用的比较多的就是；利用子集树 来进行问题的探索，就例如上图是典型的一种子集树，在最优装 载、0-1背包都是利用了这种满二叉树的子集树进行求解，然后通 过深度优先的策略，利用约束函数和上界函数，将一些不符合条件 或者不包含最优解的分支减掉，从而提高程序的效率。对于0-1背包问题我们基本上在每一个算法中都有这么一个实例，足以说明这 个问题是多么经典的一个问题啊，通过几个不同的算法求解这一问 题，我也总算对该问题有了一定的了解。助教签名实验得分附录：完整代码(回溯法)0-1背包问
5、题 回溯法求解#i nclude using namespacestd;template class Knap/Knap类记录解空间树的结点信息template friend Typep Knapsack(Typep ,Typew ,Typew,int );private :Typep Bound( int i);/计算上界的函数void Backtrack( int i);/回溯求最优解函数Typew c;/背包容量int n;/物品数Typew *w;/物品重量数组|Typep *p;/物品价值数组Typew cw;/当前重量Typep cp;/当前价值Typep bestp;/当前最后价
6、值;template Typep Knapsack(Typep p,Typew w,Typew c, int n);/声明背包问题求解函数template in li nevoid Swap (Type &a,Type & b);/ 声明交换函数template void BubbleSort(Type a, int n);/ 声明冒泡排序函数int main()int n ; /物品数int c ; /背包容量cout物品个数为：;cinn;cout背包容量为：;cin c;int *p = new int n; /物品价值 下标从1开始int *w = new int n; /物品重量 下
7、标从1开始cout物品重量分别为：e ndl;for (int i=1; i wi;cout物品价值分别为：e ndl;for (int i=1; i pi;coutvv 物品重量和价值分别为：e ndl;for (int i=1; i=n; i+)/以二元组(重量，价值)的形式输出每个物品的信息coutvv ( wi , pi );coutvve ndl;coutvv 背包能装下的最大价值为：Knapsack(p,w,c,n)void Knap:Backtrack( int i)if (in)/到达叶子节点bestp = cp;/更新最优值return ;if (cw + wi bestp)
8、Backtrack(i+1);template Typep KnapvTypew, Typep:Bound( int i) /计算上界Typew cleft = c - cw;/ 剩余容量Typep b = cp;/以物品单位重量价值递减序装入物品while (i = n & wi = cleft)cleft -= wi;b += pi;i+;/如果背包剩余容量不足以装下一个物品if (i friend Typep Knapsack(Typep,Typew ,Typew, int ); public :int operator = (Object a) const / 符号重载函数，重载 =符
9、号return (d=a.d);private :int ID; / 编号float d; /单位重量的价值;template Typep Knapsack(Typep p,Typew w,Typew c, int n)/ 为 Knap:Backtrack 初始化Typew W = 0;Typep P = 0;Object *Q =newObjectn; / 创建 Object 类的对象数组 |/初始化Object类的对象数组|for (int i=1; i=n; i+)Qi-1 .ID = i;Qi-1.d = 1.0 * pi/wi;P += pi;W += wi;if (W = c) /
10、装入所有物品return P;/依物品单位重量价值降序排序BubbleSort(Q, n);Knap K;/ 创建 Knap的对象 KK.p =n ewTypep n+1;K.w =n ewTypew n+1;for (int i=1; i=n; i+)K.pi = pQi-1D;K.wi = wQi-1.ID;/初始化KK.cp = 0;K.cw = 0;K.c = c;K.n = n;K.bestp = 0;/回溯搜索K.Backtrack(1);delete Q;delete K.w;delete K.p;return K.bestp; / 返回最优解 template void BubbleSort(Type a, int n) /记录一次遍历中是否有元素的交换bool excha nge;for (int i=0; in-1;i+)exchange = false ;for (int j=i+1; j=aj-1)Swap(aj,aj-1); exchange =true ;/如果这次遍历没有元素的交换，那么排序结束if (exchange=false )break ; template inline void Swap (Type &a,Type &b)/ 交换函数Type temp = a; a = b;b = te
