实验五--箱子装载问题(分支限界法)

实验五箱子装载问题一、实验目的：1、理解和复习所学各种算法的概念；2、掌握和复习所学各种算法的基本要素；3、掌握各种算法的优点和区别；4、通过应用范例掌握选择最佳算法的设计技巧与策略；二、实验内容及要求：1、使用贪心算法、回溯法、分支限界法解决箱子装载问题。（任选两种）2、通过上机实验进行算法实现。3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。三、实验原理：回溯法原理：从开始结点出发，以深度优先方式搜索整个解空间。这个节点成为活结点，同时也成为当前的扩展节点。在当前的扩展节点处，搜索向纵深方向一致一个新节点。贪心算法原理：贪心算法通过一系列的选择来得到问题的解。他所做的每一个选择都是当前状态下局部最好选择，即贪心选择。四、程序代码：贪心算法：#includeiostream#includestdlib.h#defineN100usingnamespacestd;intmain(){intt[N],w0[N],w[N],n,c,m,i,j;intmax=0,weight=0;booltx[N];cout请输入轮船的载重量c：endl;cinc;cout请输入可以装入的集装箱的数目n：endl;cinn;cout请输入各集装箱的重量w[i](1=i=n)：endl;for(inti=0;in;i++){cinw0[i];w[i+1]=w0[i];tx[i+1]=false;}for(i=1;in;i++){for(j=i+1;j=n;j++){if(w[i]w[j]){inttem;tem=w[j];w[j]=w[i];w[i]=tem;}}}for(i=1;i=n;i++)printf(%d,w[i]);printf(n);for(i=1;i=n;i++){intmin=weight+w[i];if(min=c){weight+=w[i];tx[i]=true;}}m=i-1;cout最优装载情况为：endl;cout装入轮船的集装箱为：;max=0;for(i=1;i=m;i++){if(tx[i]){max+=w[i];coutw[i]--;}}coutendl;cout装入的集装箱的最大重量为：maxendl;system(pause);}回溯法：#includeiostreamusingnamespacestd;classLoading{friendfloatMaxLoading(float[],float,int);public:voidBacktrack(inti);intn;int*x,*bestx;float*w,c,cw,bestw,r;};floatMaxloading(floatw1[],floatc1,floatc2,intn1,intbestx1[]){Loadingk;intj;floatMAXLoad;k.x=newint[n1+1];k.bestx=bestx1;k.w=w1;k.c=c1;k.n=n1;k.cw=0;k.bestw=0;k.r=0;for(inti=1;i=n1;i++)k.r+=w1[i];k.Backtrack(1);delete[]k.x;cout船1最优装载：k.bestwendl;MAXLoad=k.bestw;for(j=1;j=n1;j++){if(k.bestx[j]==0){MAXLoad+=w1[j];c2-=w1[j];if(c20){cout找不到合理装载方案！endl;return-1;}}}cout船1中的箱子：;for(j=1;j=n1;j++)if(k.bestx[j]==1)coutj;coutendl;cout船2中的箱子：;for(j=1;j=n1;j++)if(k.bestx[j]==0)coutj;coutendl;returnMAXLoad;}voidLoading::Backtrack(inti){if(in){if(cwbestw){for(intj=1;j=n;j++)bestx[j]=x[j];bestw=cw;}return;}r-=w[i];if(cw+w[i]=c){x[i]=1;cw+=w[i];Backtrack(i+1);cw-=w[i];}if(cw+rbestw){x[i]=0;Backtrack(i+1);}r+=w[i];}intmain(){floatw[20];floatc1,c2,k;intn,bestx[20];cout输入箱子数：;cinn;cout输入箱子重量：;for(inti=1;i=n;i++)cinw[i];cout输入容量船1，船2：;cinc1c2;k=Maxloading(w,c1,c2,n,bestx);if(k!=-1)cout总体最优装载：kendl;return1;}五、结果运行与分析：贪心算法：回溯法：六、心得与体会：通过本次实验，自己再次的联系了贪心算法和回溯法的应用，本次实验自己测试了很多次才成功，收获蛮大的，自己的编程能力进一步的提高了。