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

算法分析与设计实验报告

第五次附加实验姓名学号班级时间上午一地点 工训楼309 实验名称回溯法实验（0-1背包问题）实验目的.掌握回溯法求解问题的思想.学会利用其原理求解0-1背包问题实验原理基本思想：0-1背包问题是子集选取问题。0-1背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。基本解题步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；⑶以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。实验步骤（1）首先搜索解空间树，判断是否到达了叶结点；（2）如果左子结点是一个可行节点，就进入左子树；（3）当右子树有可能包含最优解的时候才进入右子树，计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包；（4）利用深度优先搜索整个解空间树，直到将所有的最优解找出位置。关键代码template<classTypew,classTypep>VoidKnap<Typew,Typep>::Backtrack(inti){if(i>n)■I册算法实检湮壁囚叵溯法七ero_Dπe∖Debug\zero_oπe.exeFA穹去卖验"卖验四回瓣⅛V已『口_d口e\ICtebugVero_one≡exe'F:"算法实梆实法四回溯法Azerjcme∖Debug⅛ero-cπe.exe3521物品价值分别为：⅛1074物品重量和价值分别为：¢3,9><5,10><2,7><1,4>物园2批为：5嘉I''34567物品价值分别为：12345物品重量和价值分别为：<3,1>02〉<5,3>£6,4)<7,5〉8910耀曷仝就为：工目背包登童为艇品量量务别为:1234567S910物品价值分别为：物品重量和价值分别为：<1,1><2,2>C3,3><4,4><E,5><G,6><7,7><S,B><9,9><1S,10>背包能装:E的最大价值为：55D=i;Q[i-1].d=*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)D];[i]=w[Q[i-1].ID];}〃初始化K=0;=0;=c;=n;=0;//回溯搜索(1);delete[]Q;delete[];delete[];return;//返回最优解}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;}}}template<classType>