回溯算法装载问题.doc

实验六? 回溯算法（2学时）一、实验目的与要求 1、掌握装载问题的回溯算法； 2、初步掌握回溯算法； 二、实验题 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 三、实验提示 void backtrack (int i){// 搜索第i层结点if (i n) // 到达叶结点更新最优解bestx,bestw;return;r -= w[i];if (cw + w[i] = c) {// 搜索左子树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];} 实验代码 方法1： import java.util.*; /** * 回溯法解决装载问题 * @author Administrator * */ public class demo { public static int n; //集装箱数 public static int first_weight; //第一艘载重量 public static int beautif_weight; //当前最优载重量 public static int[] arr_weight; //集装箱重量数组 public static int[] xx; // public static int[] bestxx; public static int maxLoadingRE(int[] w, int c, int[] bestx) { //递归回溯 n = w.length; first_weight = c; beautif_weight = 0; arr_weight = w; bestxx = bestx; xx = new int[n]; int r = 0; //剩余集装箱重量，未进行装载的重量 for (int i = 0; i n; i++) {r += arr_weight[i]; } trackback(0, 0, r); return beautif_weight; }//到达层数，目前装载的重量，未装载的重量 private static void trackback(int i, int cw, int r) { if (i == n) {//到达叶结点for (int j = 0; j n; j++) {bestxx[j] = xx[j];}beautif_weight = cw;return; //只是一次出栈操作，栈非空还要继续执行 } if (cw + arr_weight[i] = first_weight) { //已装载的加上要装载的小于第一个的载重量xx[i] = 0; //0代表装在第一个上，1代表装在第二个上trackback(i + 1, cw + arr_weight[i], r); //试图装载下一个集装箱，r是针对第一个装的重量，因此装在第一个里不需要减，但装在第二个时就要减去该重量 } if (r - arr_weight[i] beautif_weight) { //已装载的加上要装载的已经大于第一个的载重量，并且用总的载重量r减去当前要装载的还比最好的载重量大xx[i] = 1; //放到第二个上trackback(i + 1, cw, r - arr_weight[i]); } } public static int maxLoading(int[] w, int c, int[] bestx) { int i = 0;//当前层 int n = w.length; //层总数 int[] x = new int[n]; //x[0, i]为当前选择路径 Arrays.fill(x, -1); //初始化为-1，0表示选择第一个，1表示选择第二个 int bestw = 0;//当前最优装载重量 int[] cw = new int[n]; //当前载重量 int[] r = new int[n]; //剩余集装箱容量 int tor = 0;for (int item : w) {//item取出w中的值，进行相加tor += item; } r[0] = tor;//要装载的重量 cw[0] = 0; //搜索子树