实验3.-回溯法的应用-0-1背包等问题

实验4.回溯法的应用-0-1背包等问题实验内容本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试），通过回溯法的在实际问题求解实践中，加深理解其基本原理和思想以及求解步骤。求解的问题为0-1背包。作为挑战：可以考虑回溯法在其他问题（如最大团问题、旅行商、图的m着色问题）。实验目的理解回溯法的核心思想以及求解过程（确定解的形式及解空间组织，分析出搜索过程中的剪枝函数即约束函数与限界函数）；掌握对几种解空间树（子集树、排列数、满m叉树）的回溯方法；从算法分析与设计的角度，对0-1背包问题的基于回溯法求解有更进一步的理解。环境要求对于环境没有特别要求。对于算法实现，可以自由选择C,C++,Java，甚至于其他程序设计语言。实验步骤0-1背包;步骤1：n个物品和1个背包。对物品i，其价值为vi，重量为wi，背包容量为W。如何选取物品装入背包，使背包中所装入的物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品装入背包多次，也不能只装入部分的物品。约束条件：目标函数：步骤2：（1）物品有n种，背包容量为C，分别用p[i]和w[i]存储第i种物品的价值和重量，用x[i]标记第i种物品是否装入背包，用bestx[i]存储第i种物品的最优装载方案；（2）用递归函数Backtrack(i,cp,cw)来实现回溯法搜索子集树（形式参数i表示递归深度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前最优总价值）：niii=1maxvxniii=1iwxWx{0,1},(1in)①若in，则算法搜索到一个叶结点，判断当前总价值是否最优：1若cpbestp，更新当前最优总价值为当前总价值（即bestp=cp），更新装载方案（即bestx[i]=x[i](1≤i≤n)）；②采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）：x[i]=j；若总重量不大于背包容量（即cw+x[i]*w[i]=c），则更新当前总价br=值和总重量（即cw+=w[i]*x[i],cp+=p[i]*x[i]）,对物品i+1调用递归函数Backtrack(i+1,cp,cw)继续进行装载；函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量（即cw-=w[i]*x[i],cp-=p[i]*x[i]）；当j1时，for循环结束；③当i=1时，若已测试完所有装载方案，外层调用就全部结束；（3）主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestp和bestx[i]即为所求最大总价值和最优装载方案。步骤3：BACKTRACK-KNAPSACK-01-REC(t,w,v,W)iftn//到达叶子结点//如果找到多个解，那就择优OUTPUT(x)//x[1..n]:为问题的解，x[i]取值0或1bestp=cpreturnifcw+w[t]=W//搜索左子树x[t]=1//x[1..n]:为解向量，x[i]取值0或1cw+=w[t]//当前背包中物品的总重量cp+=v[t]//当前背包中物品的总价值BACKTRACK-KNAPSACK-01-REC(t+1,w,v,W);cw-=w[t]cp-=v[t]ifBOUND(t+1,W-cw,cp,w,v)bestp//搜索右子树x[t]=0BACKTRACK-KNAPSACK-01-REC(t+1,w,v,W)计算上界：BOUND(i,cRemained,cp,w,v)//i为第i层。//cRemained为背包的剩余容量，cp为当前背包中物品的总价值b=cpwhilei=n&&w[i]=cRemainedcRemained-=w[i]b+=v[i]i++//装满背包ifi=nb+=v[i]/w[i]*cRemainedreturnb//cp+brp步骤4：算法的正确性证明。需要这个环节，在理解的基础上对算法的正确性给予证明（这里可以略去。有兴趣可以深入一下“多米诺性质”）；步骤5：时间复杂度：O(2n)+O(n2n)=O(n2n)。步骤6：#includestdio.hintn,c,bestp;//物品的个数，背包的容量，最大价值intp[10000],w[10000],x[10000],bestx[10000];//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况voidBacktrack(inti,intcp,intcw){//cw当前包内物品重量，cp当前包内物品价值intj;if(in)//回溯结束{if(cpbestp){bestp=cp;for(i=0;i=n;i++)bestx[i]=x[i];}}elsefor(j=0;j=1;j++){x[i]=j;if(cw+x[i]*w[i]=c){cw+=w[i]*x[i];cp+=p[i]*x[i];Backtrack(i+1,cp,cw);cw-=w[i]*x[i];cp-=p[i]*x[i];}}}intmain(){inti;bestp=0;printf(请输入背包最大容量:\n);scanf(%d,&c);printf(请输入物品个数:\n);scanf(%d,&n);printf(请依次输入物品的重量:\n);for(i=1;i=n;i++)scanf(%d,&w[i]);printf(请依次输入物品的价值:\n);for(i=1;i=n;i++)scanf(%d,&p[i]);Backtrack(1,0,0);printf(最大价值为:\n);printf(%d\n,bestp);printf(被选中的物品依次是(0表示未选中，1表示选中)\n);for(i=1;i=n;i++)printf(%d,bestx[i]);printf(\n);return0;}实验总结通过这次实验，我发现自己实验过程中有很多问题，算法的复杂性分析也存在一定的问题。通过上网查询了解了回溯法，回溯法虽然是通过搜索问题的解空间来得到问题的解，但它并不是首先生成问题的所有可能解，然后再去逐一判断这些解是否满足约束条件和目标函数，而是每次只构造可能解的一部分，然后评估这部分解。如果这部分解有可能导致当前最优解，则对其进一步构造；否则，就放弃这部分解，回溯搜索其他可行解。因此，回溯法常常可以避免许多无效搜索。