10122157_项镇敏_装载问题ok实验7

实验7、装载问题问题描述与实验目的有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中第i个集装箱的重量为wi，要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。注意，在满足211ccwnii的条件下才可能将这个集装箱装上这2艘轮船。分析：用回溯法设计解装载问题的O(2^n)计算时间算法。在某些情况下该算法优于动态规划算法。用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。用可行性约束函数可剪去不满足约束条件的子树。在子集树的第j+1层的结点z处，用cw记当前的装载重量，即cw=，则当cwc1时，以结点z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。可以引入一个上界函数，用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率。设z是解空间树第i层上的当前扩展结点。cw是当前载重量；bestw是当前最优载重量；r是剩余集装箱的重量，即r=。定义上界函数为cw+r。在以z为根的子树中任一叶结点所相应的载重量均不超过cw+r。因此，当cw+r=bestw时，可将z的右子树剪去。运行结果：实验体会：算法可以在搜索子集树的过程中爆出了当前已经构造出的子集树的路径，从而可在节点搜索结束后，从子集树种与最优值相应的结点处向根结点回溯，构造出相应的最优解。如何将将计算时间复杂性限制在O(2n)是本次实验的难点。利用两种类似但结果不同的backtrack完成算法。第一次backtrack只记录当前最优解，第二次backtrack2根据最优解在记录最优装载方案。代码：#defineloading_cpp#ifdefloading_cpp#includeiostreamusingnamespacestd;templateclassTypeclassLoading{friendTypeMaxLoading(Type[],Type,int,int[]);public:voidBacktrack(inti);intn,*x,*bestx;Type*w,c,cw,bestw,r;};templateclassTypevoidLoadingType::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];}templateclassTypeTypeMaxLoading(Typew[],Typec,intn,intbestx[]){LoadingTypeX;X.x=newint[n+1];X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;X.r=0;for(inti=1;i=n;i++){X.r+=w[i];}X.Backtrack(1);delete[]X.x;returnX.bestw;}intmain(){intnumber=1,n,c1,c2,max,best;while(cinn){max=0;int*w,*p;w=newint[n+1];p=newint[n+1];for(inti=1;i=n;i++){cinw[i];p[i]=0;max+=w[i];}cinc1;cinc2;if(c1+c2=max){best=MaxLoading(w,c1,n,p);if(max-best=c2){coutCasenumberendl;coutbest;for(inti=1;i=n;i++){coutp[i];}coutendl;}else{coutCasenumberendl;coutNoendl;}}else{coutCasenumberendl;coutNoendl;}number++;delete[]w;delete[]p;}return0;}#endif