回溯算法装载问题

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

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

2、;backtrack(i+1);cw-=wli];}if(cw+r>bestw){x[i]=0;//搜索右子树backtrack(i+1);}r+=w[ij;}四、实验代码方法1:importjava.util.*;/氺氺*回溯法解决装载问题*@authorAdministrator*/publicclassdemo{publicstaticintn;//集装筘数publicstaticintfirst_weight;"第一艘载重量publicstaticintbeautif_weight;//当前最优载重景pu

3、blicstaticintf]arr_weight;//菜装筘重泉数组publicstaticint[]xx;//publicstaticint[]bestxx;publicstaticintmaxLoadingRE(int[Jw,intc,int[]bestx){//递归回溯n=w.length;first一weight=c;beautif_weight=0;arr_wcight=w;bestxx=bestx;xx=newint[nj;intr=0;//剩余集装箱秉量，未进行装载的秉Mfor(inti=();i

4、

5、eight){//己装载的加上要装载的小于第一个的裁重景xx[il=0;//0代表装在第一个上，1代表装在第二个上trackback(i+1，cw+arr_wcight[i],r);//试图裝载下一个集裝箱，r是针对第一个裝的重:量，因此装在第一个里不需要减，但装在第二个时就要减去该重景}if(r-arr_weight[i]>beautif_weight){//已装载的加I•.耍装载的已经大于弟一个的载重fi，并且用总的载重憊r减去当前要装载的还比最好的载重撒人xx[i]=1;//放到第二个上trackback(

6、i+1，cw,r-arr_wcight[i]);}publicstaticintmaxLoading(int[]w,intc,intf]bestx){inti=0;//当前Sintn=w.length;//层总数inti]x=newint[nj;//x[0,ij为当前选择路径intbestw=0;//当前最优袋载;int[Jcw=newint[nj;//当前载重景intflr=newint[nl;//剩余集装筘界辩inttor=0;for(intitem:w){//item取出w中的值，进行相加tor+=item

7、;}r[0]=tor;//要装载的重量cw[0]=0;//搜索子树while(i>-1){do{x[il+=1;if(x[i]==0){//选择放在笫一个(左子树)if(cw[i]+w[i]<=c){if(ibestw){//剪枝阑数，没奋最优解好的话x⑴会增到2,不会进入K面的if(x[ij<2)if(i

8、{r[i+1]=r[i]-w[i];cw[i+1]=cw[i];}break;}while(xlij<2);//对于放不下的在这里判断后XT能取右子树if(x[ij<2){if(i==n-1){for(intj=0;j