回溯算法装载问题.doc

_实验六 回溯算法（2学时）一、实验目的与要求1、掌握装载问题的回溯算法；2、初步掌握回溯算法；二、实验题有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。三、实验提示void backtrack (int i) / 搜索第i层结点 if (i n) / 到达叶结点 更新最优解bestx,bestw;return; r -= wi; if (cw + wi bestw) xi = 0; / 搜索右子树 backtrack(i + 1); r += wi; 4、 实验代码方法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 intn; int r = 0; /剩余集装箱重量，未进行装载的重量 for (int i = 0; i n; i+) r += arr_weighti; 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+) bestxxj = xxj; beautif_weight = cw; return; /只是一次出栈操作，栈非空还要继续执行 if (cw + arr_weighti beautif_weight) /已装载的加上要装载的已经大于第一个的载重量，并且用总的载重量r减去当前要装载的还比最好的载重量大 xxi = 1; /放到第二个上 trackback(i + 1, cw, r - arr_weighti); public static int maxLoading(int w, int c, int bestx) int i = 0; /当前层 int n = w.length; /层总数 int x = new intn; /x0, i为当前选择路径 Arrays.fill(x, -1); /初始化为-1，0表示选择第一个，1表示选择第二个 int bestw = 0; /当前最优装载重量 int cw = new intn; /当前载重量 int r = new intn; /剩余集装箱容量 int tor = 0; for (int item : w) /item取出w中的值，进行相加 tor += item; r0 = tor;/要装载的重量 cw0 = 0; /搜索子树 while (i -1) do xi += 1; if (xi = 0) /选择放在第一个（左子树） if (cwi + wi = c) if (i bestw) /剪枝函数，没有最优解好的话xi会自增到2，不会进入下面的if (xi 2) if (i n - 1) ri + 1 = ri - wi; cwi + 1 = cwi; break; while (xi 2); /对于放不下的在这里判断后才能取右子树 if (xi 2) if (i = n - 1) for (int j = 0; j n; j+) bestxj = xj; if (xi = 0) bestw = cwi + wi; else bestw = cwi; else i+; xi = -1; else /当xi=2时，说明已经遍历完两个叶节点，应向上一层继续遍历其它节点 i-; return bestw; public static void main(String args) int w = 0,10,40,40; int n = w.length; int c = 50; int bestx = new intn; System.out.println(重量分别为：); for(int ws:w) System.out.print(,+ws); System.out.println(n); int bestw = maxLoadingRE(w, c, bestx); System.out.println(回溯选择结果为: + bestw); System.out.println(Arrays.toString(bestx); 方法2：public class demo2 public static void main(String args) int n=3,m;int c=50,c2=50;int w=0,10,40,40;int bestx=new intw.length;demo2 demo2=new demo2(); m=demo2.MaxLoading(w, c, n, bestx); System.out.println(轮船的载重量分别为：);System.out.println(c(1)=+c+,c(2)=+c2);System.out.println(待装集装箱重量分别为：);System.out.print(w(i)=);for (int i=0;i=n;i+)System.out.print(，+wi);System.out.println();System.out.println(最优装载量为：);System.out.println(m(1)=+m);System.out.print(x(i)=);for (int i=0;i=n;i+)System.out.print(+bestxi);System.out.println();int m2=0;for (int j=1;jc2) System.out.println(因为m(2)大于c(2),所以原问题无解！);int MaxLoading(int w,int c,int n,int bestx)/迭代回溯法，返回最优载重量及其相应解，初始化根结点int i=1;/当前层，x1:i-1为当前路径int x=new intn+1;int bestw=0; /当前最优载重量int cw=0; /当前载重量int r=0; /剩余集装箱重量for (int j=1;j=n;j+)r+=wj;while(true)/搜索子树 while(i=n &cw+win)/到达叶结点 for (int j=1;j=n;j+)bestx