背包问题的回溯法求解实验报告

《背包问题的回溯法求解实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、实验目的（1）理解回溯法的思想。（2）掌握一些经典的问题解决方法。二、实验内容与实验步骤0-1背包问题«问题描述给定n种物品和一背包。物品i的重量是wi>0，其价值为vi>0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？«编程任务利用回溯法试设计一个算法求出0-1背包问题的解，也就是求出一个解向量ｘi(ｘi=0或１，ｘi=0表示物体ｉ不放入背包，ｘi＝1表示把物体ｉ放入背包），使得尽量多的价值装入背包。«数据输入由文件input.txt提供输入数据n，c，及每个物品的重量w[]和价值v[]。«结果输出程序运

2、行结束时，将最优解输出到文件output.txt中。输入文件示例输出文件示例input.txtoutput.txt452132121020151101三、实验环境操作系统Windows7调试软件VC++6.0上机地点综合楼2117/7四、问题分析（1）分析要解决的问题，给出你的思路，可以借助图表等辅助表达。01背包问题用回溯法实现就是要枚举其所有的解空间，时间复杂度为左右。搜索的具体方法如下：对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树：基本思想就是遍历这棵树，以枚举所有情

3、况，最后进行判断，如果重量不超过背包容量，且价值最大的话，该方案就是最后的答案。利用回溯算法写还可以加入一些优化，进行剪枝，因为很多情况是没有意义的，例如当重量大于背包容量的时候，没有必要对剩下的物品再来决策了。或者将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也是可以剪枝的。（2）分析利用你的想法解决该问题可能会有怎样的时空复杂度。时间复杂度估计：因为物品只有选与不选2个决策，而总共有n个物品，所以时间复杂度为。空间复杂度估计：7/7因为递归栈最多达到n层，而且存储所有物品的信息也只需要常数个一维数组，所以最终的空间复

4、杂度为。五、问题解决（1）根据对问题的分析，写出解决办法。根据上面的分析，搜索的具体方法如下：对于每一个物品i，对于该物品只有选与不选2个决策，总共有n个物品，可以顺序依次考虑每个物品，这样就形成了一棵解空间树，由父亲节点往下搜索的时候，往左表示选择该物品，并且将该物品的重量和价值追加到总重量和总价值中，最后，当到达第n+1层的时候，表示所有的物品都已经决策完了，可以比较和更新最优值。当所有的分支和节点都遍历完时，此时的最优值就是原问题的最优值。优化方法：剪枝一：可以进行剪枝，因为很多情况是没有意义的，当重量大于背包容量的时候，没有必要对剩下的

5、物品再来决策了。剪枝二：将剩下的所有物品都选取其总价值也没有目前已经求得的方案的价值还大的话，也可以返回。（1）描述你在进行实现时，主要的函数或操作内部的主要算法；分析这个算法的时、空复杂度，并说明你设计的巧妙之处，如有创新，将其清晰的表述。voidKnapsack(Typepp[],Typeww[],Typewc,intn){//为Knap::Backtrack初始化TypewW=0;TypepP=0;FILE*fp;Object*Q=newObject[n];for(inti=1;i<=n;i++){Q[i-1].ID=i;Q[i-1].d

6、=1.0*p[i]/w[i];P+=p[i];W+=w[i];}Sort(Q,n);//对背包里的物品按性价比排序KnapK;7/7K.p=newTypep[n+1];K.w=newTypew[n+1];K.x=newint[n+1];for(i=1;i<=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;//回溯搜索K.Backtrack(1);delete[]Q;delete[]K.w;delete

7、[]K.p;if((fp=fopen("output.txt","w"))==NULL){fprintf(stderr,"Cannotopeninputfile.");exit(0);}fprintf(fp,"%d,%d,%d,%d",K.x[4],K.x[1],K.x[2],K.x[3]);fclose(fp);cout<<"当前最优装配:";cout<voidKnap

8、::Backtrack(inti){if(i>n){bestp=cp;return;}if(cw+w[i]<=c){7/7x