回溯法 装载问题

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

1、算法设计与分析实验报告一、实验题目：将n个集装箱装上载重量为c1和c2的轮船，其中集装箱总重量

2、ticint[]x;staticint[]bestx;5算法设计与分析实验报告publicstaticintmaxloading(int[]ww,intcc,int[]xx){w=ww;c1=cc;bestw=0;cw=0;x=newint[n+1];bestx=xx;r=0;for(inti=1;i<=n;i++)r+=w[i];backtrack(1);returnbestw;}privatestaticvoidbacktrack(inti){if(i>n){if(cw>bestw){for(intj=

3、1;j<=n;j++)bestx[j]=x[j];bestw=cw;}return;}r-=w[i];if(cw+w[i]<=c1){x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+r>bestw){x[i]=0;backtrack(i+1);}r+=w[i];}publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderread=newBufferedReader(newInputStre

4、amReader(newFileInputStream("input.txt")));Stringa=newString();a=read.readLine();n=Integer.parseInt(a);System.out.println("集装箱个数:"+n);x=newint[n+1];String[]b=newString[n];a=read.readLine();System.out.println("集装箱重量:"+a);5算法设计与分析实验报告b=a.split(",");w=newint[

5、n+1];for(inti=1;i<=n;i++){w[i]=Integer.parseInt(b[i-1]);}a=read.readLine();c1=Integer.parseInt(a);a=read.readLine();c2=Integer.parseInt(a);System.out.println("轮船载重量:"+c1+","+c2);intresult=maxloading(w,c1,x);intmax,temp;for(inti=1;i<3;i++){for(intj=2;j<3;j+

6、+){if(w[i]>w[j]){temp=w[i];w[i]=w[j];w[j]=temp;}}}if((w[3]>c1)&&(w[3]>c2)){System.out.println("都不可装");}else{System.out.println("轮船1装载的集装箱：");for(intu=1;u(result+c2))System.out.println("轮船1可装："+result+""

7、+"轮船2装不完.");else{System.out.println("轮船2装载的集装箱：");for(intu=1;u

8、txt")));if((w[3]>c1)&&(w[3]>c2)){print.println("都不可装。");5算法设计与分析实验报告}else{print.println("轮船1装载的集装箱：");for(intu=1;u(result+c2))print.println("轮船1可装："+result+""+