回溯法实验(0-1背包问题)

算法分析与设计实验报告

第五次附加实验姓名学号班级时间上午地点工训楼实验名称回溯法实验（0-1背包问题）实验目的掌握回溯法求解问题的思想学会利用其原理求解背包问题实验原理基本思想：0-1背包问题是子集选取问题。0-1背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。基本解题步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；⑶以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。实验步骤（1）首先搜索解空间树，判断是否到达了叶结点；（2）如果左子结点是一个可行节点，就进入左子树；（3）当右子树有可能包含最优解的时候才进入右子树，计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包；（4）利用深度优先搜索整个解空间树，直到将所有的最优解找出位置。关键代码templatevclassTypew,classTypep>voidKnap<Typew,Typep>::Backtrack(inti){if(i>n)〃到达叶子节点{bestp=cp;〃更新最优值return;}if(cw+w[i]<=c)〃进入左子树{cw+=w[i];

cp+=p[i];Backtrack(i+1);〃回溯〃回溯结束回到当前根结点cw-=w[i];cp—=p[i]；}〃进入右子树，条件是上界值比当前最优值大，否则就将右子树剪掉if(Bound(i+1)>bestp){Backtrack(i+1);}}测试结果当输入的数据有解时:当输入的数据无解时:当输入的数据稍微大点时:

测试结果当输入的数据有解时:当输入的数据无解时:当输入的数据稍微大点时:实验分析在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我们只需要验证该程序是否正确即可。背包问题和之前的最优装载其实质上一样的，都是利用解空间树，通过深度优先搜索子集树，通过利用上界函数和一些剪枝策略，从而得到最优解。由于数据较小，所以时间上并不能反映出什么东西。实验分析在实验中并没有生成多组数据，进行比较，也没有利用随机生成函数，因为在这种有实际有关联的问题中，利用随机生成函数生成的数据是十分的不合适的，在此我们只需要验证该程序是否正确即可。背包问题和之前的最优装载其实质上一样的，都是利用解空间树，通过深度优先搜索子集树，通过利用上界函数和一些剪枝策略，从而得到最优解。由于数据较小，所以时间上并不能反映出什么东西。实验心得在这一章的回溯算法中，我们用的比较多的就是；利用子集树来进行问题的探索，就例如上图是典型的一种子集树，在最优装载、背包都是利用了这种满二叉树的子集树进行求解，然后通过深度优先的策略，利用约束函数和上界函数，将一些不符合条件或者不包含最优解的分支减掉，从而提高程序的效率。对于背包问题我们基本上在每一个算法中都有这么一个实例，足以说明这个问题是多么经典的一个问题啊，通过几个不同的算法求解这一问题，我也总算对该问题有了一定的了解。实验得分助教签名附录：完整代码(回溯法)//0-1背包问题回溯法求解#include<iostream>usingnamespacestd;template<classTypew,classTypep>classKnap//Knap类记录解空间树的结点信息{template<classTypew,classTypep>friendTypepKnapsack(Typep[],Typew[],Typew,int);private:TypepBound(inti);//计算上界的函数voidBacktrack(inti);//回溯求最优解函数Typewc;//背包容量intn;//物品数Typew*w;〃物品重量数组；Typep*p;//物品价值数组Typewcw;//当前重量Typepcp;//当前价值Typepbestp;//当前最后价值};template<classTypew,classTypep>TypepKnapsack(Typepp[],Typeww[],Typewc,intn);//声明背包问题求解函数template<classType>inlinevoidSwap(Type&a,Type&b);//声明交换函数template<classType>voidBubbleSort(Typea[],intn);//声明冒泡排序函数intmain(){intn;//物品数intc;//背包容量cout<<"物品个数为："；cin>>n;cout<<"背包容量为：”；cin>>c;int*p=newint[n];〃物品价值下标从1开始int*w=newint[n];〃物品重量下标从1开始cout<<"物品重量分别为："<<endl;for(inti=1;i<=n;i++){cin>>w[i];}cout<<"物品价值分别为："<<endl;for(inti=1;i<=n;i++)//以二元组(重量，价值)的形式输出每物品的信息{cin>>p[i];}cout<<"物品重量和价值分别为："<<endl;for(inti=1;i<=n;i++)//以二元组(重量，价值)的形式输出每个物品的信息{cout<<"("<<w[i]<<","<<p[i]<<")";}cout<<endl;cout<<"背包能装下的最大价值为："<<Knapsack(p,w,c,n)<<endl;〃输出结果system("pause");return0;}template<classTypew,classTypep>voidKnap<Typew,Typep>::Backtrack(inti){if(i>n)//到达叶子节点{bestp=cp;//更新最优值return;}if(cw+w[i]<=c)//进入左子树{cw+=w[i];cp+=p[i];Backtrack(i+1);//回溯//回溯结束回到当前根结点cw-=w[i];cp-=p[i];}//进入右子树，条件是上界值比当前最优值大，否则就将右子树剪掉if(Bound(i+1)>bestp){Backtrack(i+1);}}template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti)//计算上界{Typewcleft=c-cw;//剩余容量Typepb=cp;//以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//如果背包剩余容量不足以装下一个物品if(i<=n){b+=p[i]/w[i]*cleft;//则将物品的部分装入到背包中}returnb;}classObject//定义对象类，作用相当于结构体{template<classTypew,classTypep>friendTypepKnapsack(Typep[],Typew[],Typew,int);public:intoperator>=(Objecta)const//符号重载函数，重载>=符号{return(d>=a.d);}private:intID;//编号floatd;//单位重量的价值};template<classTypew,classTypep>TypepKnapsack(Typepp[],Typeww[],Typewc,intn){〃为Knap::Backtrack初始化TypewW=0;TypepP=0;Object*Q=newObject[n];〃创建Object类的对象数组；〃初始化Object类的对象数组；for(inti=1;i<=n;i++){Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)〃装入所有物品{returnP;}//依物品单位重量价值降序排序BubbleSort(Q,n);Knap<Typew,Typep>K;〃创建Knap的对象KK.p=newTypep[n+1];

K.w=newTypew[n+1];for(inti=1;i<=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-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;returnK.bestp;//返回最优解}template<classType>voidBubbleSort(Typea[],intn){//记录一次遍历中是否有元素的交换boolexchange;for(inti=0;i<n-1;i++){exchange=false;for(intj=i+1;j<=n-1;j++){/r/