回溯算法 01背包问题

淮海工学院计算机工程学院实验报告书课程名：《算法分析与设计》题目：实验4回溯算法0/1背包问题班级：软件081班学号：110831116姓名：陈点点评语：成绩：指导教师：批阅时间：年月日《算法分析与设计》实验报告-1-实验4回溯算法实验目的和要求（1）掌握回溯法的设计思想；（2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；（3）考察回溯法求解问题的有效程度。（4）设计可能解的表示方式，构成解空间树；（5）设计回溯算法完成问题求解；（6）设计测试数据，统计搜索空间的结点数；实验内容给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值最大。实验环境TurboC或VC++实验学时2学时，必做实验数据结构与算法递归法：1，X={};2，flag=false;3，advance(1);4，if(flag)输出解X;else输出“无解”;advance(intk)1,对每一个x∈Sk循环执行下列操作1.1xk=x;1.2将xk加入X;1.3if(X是最终解)flag=true;return;1.4elseif(X是部分解)advance(k+1);迭代法：1，X={};2，Flag=false;jikka《算法分析与设计》实验报告-2-3，K=1;4，While(k=1)4.1当(Sk没有被穷举)循环执行下列操作4.1.1xk=Sk中的下一个元素;4.1.2将xk加入X;4.1.3if(X为最终解)flag=true;转步骤5;4.1.4elseif(X是部分解)k=k+1;转步骤4;4.2重置Sk，使得下一个元素排在第一位;4.3k=k-1;5，if(flag)输出解X;else输出“无解”;核心源代码递归法：#includestdio.hintc;//背包容量intn;//物品数intweight[100];//存放n个物品重量的数组intprice[100];//存放n个物品价值的数组intcurrentWeight=0;//当前重量intcurrentPrice=0;//当前价值intbestPrice=0;//当前最优值intbestAnswer[100];//当前最优解intbp=0;intbA[100];//当前最优解inttimes=0;voidPrint();voidBacktracking(inti){times+=1;if(in){Print();if(bestPricebp){bp=bestPrice;for(intj=1;j=n;j++)bA[j]=bestAnswer[j];}return;}《算法分析与设计》实验报告-3-if(currentWeight+weight[i]=c){//将物品i放入背包，搜索左子树bestAnswer[i]=1;currentWeight+=weight[i];bestPrice+=price[i];Backtracking(i+1);//完成上面的递归，返回到上一结点，物品i不放入背包，准备递归右子树currentWeight-=weight[i];bestPrice-=price[i];}bestAnswer[i]=0;Backtracking(i+1);}voidPrint(){inti;printf(\n路径为{);for(i=1;in;++i)printf(%d,,bestAnswer[i]);printf(%d}\t价值为%d\n,bestAnswer[i],bestPrice);}voidmain(){inti;/*输入部分*/printf(请输入物品的数量:\n);scanf(%d,&n);printf(请输入背包的容量(能承受的重量):\n);scanf(%d,&c);printf(请依次输入%d个物品的重量:\n,n);for(i=1;i=n;i++)scanf(%d,&weight[i]);printf(请依次输入%d个物品的价值:\n,n);for(i=1;i=n;i++)scanf(%d,&price[i]);printf(各符合条件的路径为：\n);Backtracking(1);printf(*******************************************************\n);printf(\nthebestansweris{);for(i=1;in;++i)printf(%d,,bA[i]);printf(%d}\tthepriceis%d\n,bA[i],bp);printf(\n\n总共搜索结点数%d\n,times);}《算法分析与设计》实验报告-4-迭代法：#includestdio.hintc;//背包容量intm;//物品数intx[100];intweight[100];//物品重量intprice[100];//物品价值intbp=0;intbA[100];//当前最优解inttimes=0;voidbeibao(intn){inti,k;for(i=1;i=n;i++)//初始化x[i]=0;k=1;while(k=1){times+=1;x[k]=x[k]+1;//第k个物品放入背包if(x[k]=2&&k==m){//得到一个解，输出intcurrentWeight=0;//当前重量intcurrentPrice=0;//当前价值for(i=1;i=n;i++){if(x[i]==1){currentWeight+=weight[i];currentPrice+=price[i];《算法分析与设计》实验报告-5-}}if(currentWeight=c){if(currentPricebp){bp=currentPrice;for(intj=1;j=n;j++){if(x[j]==2)bA[j]=x[j]-2;elsebA[j]=x[j];}}}}elseif(x[k]=2&&km)k=k+1;//放置下一个物品else{x[k]=0;//拿走第k个物品，重置x[k]，回溯k=k-1;}}}voidmain(){inti;/*输入部分*/printf(请输入物品的数量:\n);scanf(%d,&m);《算法分析与设计》实验报告-6-printf(请输入背包的容量(能承受的重量):\n);scanf(%d,&c);printf(请依次输入%d个物品的重量:\n,m);for(i=1;i=m;i++)scanf(%d,&weight[i]);printf(请依次输入%d个物品的价值:\n,m);for(i=1;i=m;i++)scanf(%d,&price[i]);beibao(m);printf(*******************************************************\n);printf(\nthebestansweris{);for(i=1;im;++i)printf(%d,,bA[i]);printf(%d}\tthepriceis%d\n,bA[i],bp);printf(\n\n总共搜索结点数%d\n,times);}实验结果迭代法：《算法分析与设计》实验报告-7-递归法：物品情况搜索结点数递归法n=3w=20,15,10;c=25v=20,30,25;11迭代法21递归法n=3w=20,16,10;c=25v=20,30,25;10迭代法21递归法n=4w=10,20,30,40;c=30v=4,3,2,1;17迭代法45递归法n=4w=30,25,10,35c=40v=7,9,3,619迭代法45递归法n=4w=7,3,4,5c=10v=42,12,40,2522迭代法45《算法分析与设计》实验报告-8-由表格可看出，递归法的搜索空间结点数要比迭代法少，因此递归法的空间性能好。实验体会通过这次试验，我掌握了回溯法的设计思想，如何构造解空间树，如何储存求解路径。递归的思想：（1）考虑物品i被选择，这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后，继续递归去考虑其余物品的选择。（2）考虑物品i不被选择，这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。迭代的思想：对物品i的考察有这样几种情况：当该物品被包含在候选解中依旧满足解的总重量的限制，该物品被包含在候选解中是应该继续考虑的；反之，该物品不应该包括在当前正在形成的候选解中。同样地，仅当物品不被包括在候选解中，还是有可能找到比目前临时最佳解更好的候选解时，才去考虑该物品不被包括在候选解中；反之，该物品不包括在当前候选解中的方案也不应继续考虑。