回溯算法裝載問題

1、實驗六  回溯算法（2學時） 一、實驗目的與要求1、掌握裝載問題的回溯算法；2、初步掌握回溯算法；二、實驗題有一批共n個集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且 裝載問題要求確定是否有一個合理的裝載方案可將這個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。三、實驗提示void backtrack (int i) / 搜索第i層結(jié)點 if (i > n) / 到達葉結(jié)點 更新最優(yōu)解bestx,bestw;return; r -= wi; if (cw + wi <= c) / 搜索左子樹 xi = 1; cw += wi; ba

2、cktrack(i + 1); cw -= wi; if (cw + r > bestw) xi = 0; / 搜索右子樹 backtrack(i + 1); r += wi; 4、 實驗代碼方法1：import java.util.*;/* * 回溯法解決裝載問題 * author Administrator * */ public class demo public static int n; /集裝箱數(shù) public static int first_weight; /第一艘載重量 public static int beautif_weight; /當前最優(yōu)載重量 public

3、static int arr_weight; /集裝箱重量數(shù)組 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+

4、) r += arr_weighti; trackback(0, 0, r); return beautif_weight; /到達層數(shù)，目前裝載的重量，未裝載的重量 private static void trackback(int i, int cw, int r) if (i = n) /到達葉結(jié)點 for (int j = 0; j < n; j+) bestxxj = xxj; beautif_weight = cw; return; /只是一次出棧操作，棧非空還要繼續(xù)執(zhí)行 if (cw + arr_weighti <= first_weight) /已裝載的加上要裝載的

5、小于第一個的載重量 xxi = 0; /0代表裝在第一個上，1代表裝在第二個上 trackback(i + 1, cw + arr_weighti, r); /試圖裝載下一個集裝箱，r是針對第一個裝的重量，因此裝在第一個里不需要減，但裝在第二個時就要減去該重量 if (r - arr_weighti > beautif_weight) /已裝載的加上要裝載的已經(jīng)大于第一個的載重量，并且用總的載重量r減去當前要裝載的還比最好的載重量大 xxi = 1; /放到第二個上 trackback(i + 1, cw, r - arr_weighti); public static int maxL

6、oading(int w, int c, int bestx) int i = 0; /當前層 int n = w.length; /層總數(shù) int x = new intn; /x0, i為當前選擇路徑 Arrays.fill(x, -1); /初始化為-1，0表示選擇第一個，1表示選擇第二個 int bestw = 0; /當前最優(yōu)裝載重量 int cw = new intn; /當前載重量 int r = new intn; /剩余集裝箱容量 int tor = 0; for (int item : w) /item取出w中的值，進行相加 tor += item; r0 = tor;/要

7、裝載的重量 cw0 = 0; /搜索子樹 while (i > -1) do xi += 1; if (xi = 0) /選擇放在第一個（左子樹） if (cwi + wi <= c) if (i < n - 1) cwi + 1 = cwi + wi; ri + 1 = ri; break; /能放下就直接跳出這個do-while循環(huán) else /選擇放在第二個（右子樹） if (ri - wi > bestw) /剪枝函數(shù)，沒有最優(yōu)解好的話xi會自增到2，不會進入下面的if (xi < 2) if (i < n - 1) ri + 1 = ri - wi

8、; 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時，說明已經(jīng)遍歷完兩個葉節(jié)點，應向上一層繼續(xù)遍歷其它節(jié)點 i-; return bestw; public static void main(String args) int

9、 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("回溯選擇結(jié)果為: " + bestw); System.out.print

10、ln(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+&q

11、uot;,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("最優(yōu)裝載量為：");System.out.println("m(1)="+m);System.out.print("x(i)

12、=");for (int i=0;i<=n;i+)System.out.print(""+bestxi);System.out.println("");int m2=0;for (int j=1;j<=n;j+)m2=m2+wj*(1-bestxj); System.out.println("回溯選擇結(jié)果為:"+m2);if(m2>c2) System.out.println("因為m(2)大于c(2),所以原問題無解！");int MaxLoading(int w,int c,int n,int bestx)/迭代回溯法，返回最優(yōu)載重量及其相應解，初始化根結(jié)點int i=1;/當前層，x1:i-1為當前路徑int x=new intn+1;int bestw=0; /當前最優(yōu)載重量int cw=0; /當前載重量int r=0; /剩余集裝箱重量for (int j=1;j<=n;j+)r+=wj;while(true)/搜索子樹 while(i<=n &&cw+wi<=c)/進入左子樹r-=wi;cw+=wi;xi=1;i+;