《回溯法 装载问题.doc》由会员分享,可在线阅读,更多相关《回溯法 装载问题.doc(5页珍藏版)》请在金锄头文库上搜索。
1、算法设计与分析实验报告一、实验题目:将n个集装箱装上载重量为c1和c2的轮船,其中集装箱总重量c1+c2,使用回溯法求出最优装载方案。二、实验流程图:三、实验结果:input.txtoutput.txt四、源程序:package javaapplication1;import java.io.*;public class Main static int n; static int w; static int c1,c2; static int cw; static int bestw; static int r; static int x; static int bestx; public s
2、tatic int maxloading(intww,int cc,intxx) w=ww; c1=cc; bestw=0; cw=0; x=new intn+1; bestx=xx; r=0; for(int i=1;in) if(cwbestw) for(int j=1;j=n;j+) bestxj=xj; bestw=cw; return; r-=wi; if(cw+wibestw) xi=0; backtrack(i+1); r+=wi; public static void main(String args) throws IOException BufferedReader rea
3、d =new BufferedReader(new InputStreamReader(new FileInputStream(input.txt); String a=new String(); a=read.readLine(); n=Integer.parseInt(a); System.out.println(集装箱个数: +n); x=new intn+1; Stringb=new Stringn; a=read.readLine(); System.out.println(集装箱重量: +a); b=a.split(,); w=new intn+1; for(int i=1;i=n
4、;i+) wi=Integer.parseInt(bi-1); a=read.readLine(); c1=Integer.parseInt(a); a=read.readLine(); c2=Integer.parseInt(a); System.out.println(轮船载重量: +c1+,+c2); int result= maxloading(w,c1,x); int max,temp; for(int i=1;i3;i+) for(int j=2;jwj) temp=wi; wi=wj; wj=temp; if(w3c1)&(w3c2) System.out.println(都不可
5、装); elseSystem.out.println(轮船1装载的集装箱:); for (int u=1;u(result+c2) System.out.println(轮船1可装:+result+ +轮船2装不完.); else System.out.println(轮船2装载的集装箱:); for (int u=1;uc1)&(w3c2) print.println(都不可装。); else print.println(轮船1装载的集装箱:); for (int u=1;u(result+c2) print.println(轮船1可装:+result+ +轮船2装不完。); else print.println(轮船2装载的集装箱:); for (int u=1;un+1;u+) if(bestxu=0) print.println(u+ ); print.println(最优装载-轮船1:+result+ +轮船2:+(r-result); read.close(); print.close(); 5