回溯算法装载问题.doc

《回溯算法装载问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.实验六 回溯算法（2学时） 一、实验目的与要求1、掌握装载问题的回溯算法；2、初步掌握回溯算法；二、实验题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。三、实验提示voidbacktrack(inti){//搜索第i层结点if(i>n)//到达叶结点更新最优解bestx,bestw;return;r-=w[i];if(cw+w[i]<=c){//搜索左子树x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(c

2、w+r>bestw){x[i]=0;//搜索右子树backtrack(i+1);}r+=w[i];}四、实验代码方法1：importjava.util.*;/***回溯法解决装载问题*@authorAdministrator**/publicclassdemo{publicstaticintn;//集装箱数publicstaticintfirst_weight;//第一艘载重量publicstaticintbeautif_weight;//当前最优载重量publicstaticint[]arr_weight;//集装箱重量数组publicstaticint[]xx;//publi

3、cstaticint[]bestxx;..publicstaticintmaxLoadingRE(int[]w,intc,int[]bestx){//递归回溯n=w.length;first_weight=c;beautif_weight=0;arr_weight=w;bestxx=bestx;xx=newint[n];intr=0;//剩余集装箱重量，未进行装载的重量for(inti=0;i

4、aticvoidtrackback(inti,intcw,intr){if(i==n){//到达叶结点for(intj=0;j

5、在第二个时就要减去该重量}if(r-arr_weight[i]>beautif_weight){//已装载的加上要装载的已经大于第一个的载重量，并且用总的载重量r减去当前要装载的还比最好的载重量大xx[i]=1;//放到第二个上trackback(i+1,cw,r-arr_weight[i]);}}publicstaticintmaxLoading(int[]w,intc,int[]bestx){inti=0;//当前层intn=w.length;//层总数..int[]x=newint[n];//x[0,i]为当前选择路径Arrays.fill(x,-1);//初始化为-1，0

6、表示选择第一个，1表示选择第二个intbestw=0;//当前最优装载重量int[]cw=newint[n];//当前载重量int[]r=newint[n];//剩余集装箱容量inttor=0;for(intitem:w){//item取出w中的值，进行相加tor+=item;}r[0]=tor;//要装载的重量cw[0]=0;//搜索子树while(i>-1){do{x[i]+=1;if(x[i]==0){//选择放在第一个（左子树）if(cw[i]+w[i]<=c){if(i

7、接跳出这个do-while循环}}else{//选择放在第二个（右子树）if(r[i]-w[i]>bestw){//剪枝函数，没有最优解好的话x[i]会自增到2，不会进入下面的if(x[i]<2)if(i