回溯法 装载问题

将n个集装箱装上载重量为c1和c2的轮船，其中集装箱总重量二、实验流程图：

static int n; static int[] w; static int c; static int cw; static int bestw; static int r; static int[] x; static int[] bestx;beginBufferedReader read =new BufferedReader(new InputStreamReader(new FileInputStream(\"inputint bestw1;.txt\")));String s=new String(); s=read.readLine(); n=Integer.parseInt(s); int []bestx1=new int string[]b=new [n+1];String[n]; s=read.readLine(); b=s.split(\ w=new int[n+1];int i=1i<=n;w[i]=Integer.parseInt(b[i-1]);Ni++;s=read.readLine();Y c=Integer.parseInt(s); int[] x = new int[w.length]; Loading load = new Loading(); load.maxLoading(w,c,x);bestw1=bestw; bestw=0; cw=0; r=0;int i = 1;i <=n;s=read.readLine(); c=Integer.parseInt(s)public int ;maxLoading(int[] ww,int cc,int[] xx)PrintWriter print=new load.maxLoading(w,c,xPrintWriter(new );OutputStreamWriter(ne n = ww.length-1;w System.out.print w = ww;FileOutputStream(\"outln(\"轮船1装载的 c = cc;put.txt\")));集装箱：); cw = 0;for (int u=1;u nYbestx[j] = x[j];bestw = cw;Nreturn;r -= w[i];i <=n;System.out.Yprintln(bestx1[i]);print.println(bestx1[i]);i++NSystem.out.println(\"轮船1装载的集装箱：\");int i = 1;r += w[i];Nbacktrace(0);cw + w[i] <= cY x[i] = 1; cw += w[i];backtrace(i+1);return bestw;Ncw -= w[i];i <=n; bestx1[i]=bestx[i];i++Nint j=1;System.out.Yprintln(bestx[i]);print.println(bestx[i]);NSystem.out.println(\"轮i++;船2装载的集装箱：\"); for (int =1;u bestwYx[i] = 0;Nbacktrace(i+1);j<=n;Ybestx[j]==1Yw[j]=0;Nj++r += w[i];

算法设计与分析实验报告

三、实验结果：

input.txt

output.txt

四、源程序：

2

算法设计与分析实验报告

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 static int maxloading(int[]ww,int cc,int[]xx){

w=ww;

3

算法设计与分析实验报告

c1=cc;

bestw=0;

cw=0;

x=new int[n+1];

bestx=xx;

r=0;

for(int i=1;i<=n;i++)

r+=w[i];

backtrack(1);

return bestw;

}

private static void backtrack(int i){

if(i>n){ if(cw>bestw){

4

算法设计与分析实验报告

for(int j=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){

5

算法设计与分析实验报告

x[i]=0;

backtrack(i+1);

}

r+=w[i]; }

public static void main(String[] args) throws IOException {

BufferedReader read =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 int[n+1];

String[]b=new String[n];

a=read.readLine();

6

算法设计与分析实验报告

System.out.println(\"集装箱重量: \"+a);

b=a.split(\

w=new int[n+1];

for(int i=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+\

int result= maxloading(w,c1,x);

int max,temp;

7

算法设计与分析实验报告

for(int i=1;i<3;i++){

for(int j=2;j<3;j++){

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装载的集装箱：\");

8

算法设计与分析实验报告

for (int u=1;uif(bestx[u]==1)

System.out.println(u+\" \");

if(r>(result+c2))

System.out.println(\"轮船1可装：\"+result+\" \"+\"轮船2装不完.\");

else{

System.out.println(\"轮船2装载的集装箱：\");

for (int u=1;uif(bestx[u]==0)

System.out.println(u+\" \");

System.out.println(\"最优装载--轮船1:\"+result+\" \"+\"轮船2:\"+(r-result));

}

9

算法设计与分析实验报告

}

PrintWriter print=new PrintWriter(new OutputStreamWriter(new

FileOutputStream(\"output.txt\")));

if((w[3]>c1)&&(w[3]>c2)){

print.println(\"都不可装。\");

}

else{

print.println(\"轮船1装载的集装箱：\");

for (int u=1;uif(bestx[u]==1)

print.println(u+\" \");

if(r>(result+c2))

print.println(\"轮船1可装：\"+result+\" \"+\"轮船2装不完。 else{

10

\");

算法设计与分析实验报告

print.println(\"轮船2装载的集装箱：\");

for (int u=1;uif(bestx[u]==0)

print.println(u+\" \");

print.println(\"最优装载--轮船1:\"+result+\"

}

}

read.close();

print.close();

}

}

11

轮船2:\"+(r-result));

\"+\"