java算法分析与设计之集装箱装载问题源代码

public class Test10 { /** * 集装箱装载问题 */ //类数据成员 static int n; //集装箱数 static int[] w; //集装箱重量数组 static int c; //第一艘轮船的载重量 static int cw; //当前载重量 static int bestw; //当前最优载重量 static int r; //剩余集装箱重量 static int [] x; //当前解 static int [] bestx; //当前最优解 public static void main(String[] args) { int[]w1={10,20,20}; //集装箱重量数组 int c1=40; //第一艘轮船的载重量 int [] x1={0,0,0}; maxLoading(w1,c1,x1); System.out.println("最优载重量为："+bestw); for (int i=0;i<w1.length;i++) System.out.print(bestx[i]+" "); } public static int maxLoading(int []ww,int cc,int [] xx) { //初始化类数据成员 n=ww.length-1; w=ww; c=cc; cw=0; bestw=0; x=new int[n+1]; bestx=xx; r=0; //初始化r for(int i=1;i<=n;i++) r+=w[i]; //计算最优载重量 backtrack(1); return bestw; } //回溯算法 private static void backtrack(int i) {//搜索第i层结点 if(i>n){//到达叶结点 for(int j=1;j<=n;j++) bestx[j]=x[j]; bestw=cw; return; } //搜索子树 r-=w[i]; if(cw+w[i]<=c){//搜索左子树，即x[i]=1 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]; } }