算法设计与分析 回溯算法 实验报告

武夷学院实验报告课程名称：算法设计与分析实验题目：回溯算法学生班级：09级计科一班学生姓名：学生学号：200940110指导教师：李晓飞完成日期：2011.11.24数学与计算机系

实验七

回溯算法一、实验目的与要求1、掌握装载问题的回溯算法；2、初步掌握回溯算法；二、实验题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱I的重量为wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。三．实验步骤1.程序输入：importjava.util.*;publicclasshuisuo{ publicstaticintnn; publicstaticintcc; publicstaticintbestww; publicstaticint[]ww; publicstaticint[]xx; publicstaticint[]bestxx; publicstaticintmaxLoadingRE(int[]w,intc,int[]bestx){ nn=w.length; cc=c; bestww=0; ww=w; bestxx=bestx; xx=newint[nn]; intr=0; for(inti=0;i<nn;i++){ r+=ww[i]; } trackback(0,0,r); returnbestww; } privatestaticvoidtrackback(inti,intcw,intr){/ if(i==nn){ for(intj=0;j<nn;j++){ bestxx[j]=xx[j]; } bestww=cw; return; } if(cw+ww[i]<=cc){ xx[i]=0; trackback(i+1,cw+ww[i],r); } if(r-ww[i]>bestww){ xx[i]=1; trackback(i+1,cw,r-ww[i]); } } publicstaticintmaxLoading(int[]w,intc,int[]bestx){ inti=0; intn=w.length; int[]x=newint[n]; Arrays.fill(x,-1); intbestw=0; int[]cw=newint[n]; int[]r=newint[n]; inttor=0; for(intitem: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<n-1){ cw[i+1]=cw[i]+w[i]; r[i+1]=r[i]; } break; } } else{ if(r[i]-w[i]>bestw){ if(i<n-1){ r[i+1]=r[i]-w[i]; cw[i+1]=cw[i]; } break; } } }while(x[i]<2); if(x[i]<2){ if(i==n-1){ for(intj=0;j<n;j++){ bestx[j]=x[j]; } if(x[i]==0){ bestw=cw[i]+w[i]; } else{ bestw=cw[i]; } } else{ i++; x[i]=-1; } } else{ i--; } } returnbestw; } publicstaticvoidmain(String[]args){ int[]w={20,10,40}; intn=w.length; intc=50; int[]bestx=newint[n]; intbestw=maxLoadingRE(w,c,bestx); System.out.println("bestw:"+