回溯算法裝載問題

1、實(shí)驗(yàn)六  回溯算法（2學(xué)時(shí)） 一、實(shí)驗(yàn)?zāi)康呐c要求1、掌握裝載問題的回溯算法；2、初步掌握回溯算法；二、實(shí)驗(yàn)題有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且 裝載問題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。三、實(shí)驗(yàn)提示void backtrack (int i) / 搜索第i層結(jié)點(diǎn) if (i > n) / 到達(dá)葉結(jié)點(diǎn) 更新最優(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、 實(shí)驗(yàn)代碼方法1：import java.util.*;/* * 回溯法解決裝載問題 * author Administrator * */ public class demo public static int n; /集裝箱數(shù) public static int first_weight; /第一艘載重量 public static int beautif_weight; /當(dāng)前最優(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; /剩余集裝箱重量，未進(jìn)行裝載的重量 for (int i = 0; i < n; i+

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

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

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

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

8、; cwi + 1 = cwi; break; while (xi < 2); /對(duì)于放不下的在這里判斷后才能取右子樹 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 /當(dāng)xi=2時(shí)，說明已經(jīng)遍歷完兩個(gè)葉節(jié)點(diǎn)，應(yīng)向上一層繼續(xù)遍歷其它節(jié)點(diǎn) 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("因?yàn)閙(2)大于c(2),所以原問題無解！");int MaxLoading(int w,int c,int n,int bestx)/迭代回溯法，返回最優(yōu)載重量及其相應(yīng)解，初始化根結(jié)點(diǎn)int i=1;/當(dāng)前層，x1:i-1為當(dāng)前路徑int x=new intn+1;int bestw=0; /當(dāng)前最優(yōu)載重量int cw=0; /當(dāng)前載重量int r=0; /剩余集裝箱重量for (int j=1;j<=n;j+)r+=wj;while(true)/搜索子樹 while(i<=n &&cw+wi<=c)/進(jìn)入左子樹r-=wi;cw+=wi;xi=1;i+;