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

算法分析与设计实验报告第五次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称回溯法实验(0-1背包问题)实验目的掌握回溯法求解问题的思想学会利用其原理求解0-1背包问题实验原理基本思想：0-1背包问题是子集选取问题。0-1背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。基本解题步骤：针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。实验步骤（1）首先搜索解空间树，判断是否到达了叶结点；（2）如果左子结点是一个可行节点，就进入左子树；（3）当右子树有可能包含最优解的时候才进入右子树，计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包；（4）利用深度优先搜索整个解空间树，直到将所有的最优解找出位置。关键代码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);}}测试结果当输入的数据有解时：当输入的数据无解时：当输入的数据稍微大点时：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++){if(a[j]>=a[j-1]){Swap(a[j],a[j-1]);exchange=true;}}//如果这次遍历没有元素的交换，那么排序结束if(exchange==false){break