一、回溯法

? ? ? ? 回溯法采用DFS＋剪枝的方式，通過(guò)剪枝刪掉不滿(mǎn)足條件的樹(shù)，提高本身作為窮舉搜索的效率。

? ? ? ? 回溯法一般有子集樹(shù)和排列樹(shù)兩種方式，下面的裝載問(wèn)題和01背包問(wèn)題屬于子集樹(shù)的范疇。

解空間類(lèi)型：

? ? ? ? 子集樹(shù)：所給的問(wèn)題是從n個(gè)元素的集合S中找出滿(mǎn)足某種性質(zhì)的子集，例如裝載問(wèn)題、0-1背包問(wèn)題。

? ? ? ? 排列樹(shù)：所給的問(wèn)題是確定n個(gè)元素滿(mǎn)足某種性質(zhì)的排列，例如旅行商問(wèn)題。

????????回溯法所搜索的解結(jié)果，都在樹(shù)的葉子結(jié)點(diǎn)上，一般左樹(shù)為添加元素（1），右樹(shù)為不添加元素（0）。

剪枝策略：

????????左剪枝：當(dāng)前擴(kuò)展節(jié)點(diǎn)，加入左枝后，不符合約束條件要求，那么就直接剪掉這個(gè)子節(jié)點(diǎn)及其所有子樹(shù)，不再繼續(xù)搜索。

? ? ? ? 右剪枝：當(dāng)前擴(kuò)展節(jié)點(diǎn)，加入右枝后，已經(jīng)無(wú)法繼續(xù)尋求最優(yōu)解，后續(xù)子樹(shù)也無(wú)法存在最優(yōu)解，或者相比于之前遍歷的葉子結(jié)點(diǎn)來(lái)說(shuō)，更好的最優(yōu)解，那么就剪掉這個(gè)子節(jié)點(diǎn)及其所有子樹(shù)，不再繼續(xù)搜索。

二、簡(jiǎn)單裝載問(wèn)題

1、算法設(shè)計(jì)

? ? ? ? 簡(jiǎn)單裝載問(wèn)題：n個(gè)集裝箱裝進(jìn)一艘載重量為W的輪船，其中集裝箱的重量為,不考慮集裝箱體積。設(shè)計(jì)一個(gè)算法，要求選擇若干集裝箱裝進(jìn)輪船，使得不超過(guò)載重量W，且給出可行解，和最優(yōu)解的箱子裝載方式。

? ? ? ? 算法：回溯法，子集樹(shù)算法。

? ? ? ? 算法參數(shù)表：

????????????????num：選擇的集裝箱數(shù)

? ? ? ? ? ? ? ? tw：選擇的集裝箱重量和

? ? ? ? ? ? ? ? rw：剩余的集裝箱重量和

? ? ? ? ? ? ? ? op：表示是否選擇該集裝箱，op=1則選擇，op=0則不選

? ? ? ? ? ? ? ? x[ ]：最優(yōu)解的op操作符選擇，可以用來(lái)輸出最優(yōu)的集裝箱裝載方案

? ? ? ? 靜態(tài)變量：

? ? ? ? ? ? ? ? n：物品個(gè)數(shù)

? ? ? ? ? ? ? ? w[ ]：各種物品的重量

? ? ? ? ? ? ? ? W：輪船總重量限額

? ? ? ? ? ? ? ? minnum：最優(yōu)解集裝箱存放個(gè)數(shù)

? ? ? ? ? ? ? ? maxw：最優(yōu)解的總重量

? ? ? ? dfs策略：

（1）先判斷是否為葉子結(jié)點(diǎn)，若是則判斷該解是否為最優(yōu)解，若是最優(yōu)解則把op數(shù)組存入x數(shù)組。最優(yōu)解條件：當(dāng)前解集裝箱存放個(gè)數(shù)是否小于最優(yōu)解集裝箱存放個(gè)數(shù)，且選擇的集裝箱和小于輪船限額

（2）若不是葉子結(jié)點(diǎn)則進(jìn)行擴(kuò)展操作。

（3）先進(jìn)行左擴(kuò)展，若tw+w[i]<=W，即加入這個(gè)物品后，總重量不大于輪船限額，則繼續(xù)擴(kuò)展，否則剪枝。

（4）再進(jìn)行右擴(kuò)展，若tw+rw-w[i]>=W，即不加入這個(gè)物品時(shí)，所選集裝箱總重和未選集裝箱總重的和仍然不小于輪船限額，則繼續(xù)擴(kuò)展，否則剪枝。

2、代碼

//回溯法最優(yōu)裝載問(wèn)題
public class bestload {static int n=5;static int minnum=9999;static int W=10;      //w為每個(gè)箱子重量static int maxw=0;    //存放最優(yōu)解總重量static int w[]={0,5,2,6,4,3};public static void main(String []args){int rw=0;                   //rw為剩余集裝箱重量和for(int num:w)rw+=num;int op[]=new int[w.length];  //存放一個(gè)箱子是否裝載int x[]=new int[w.length];System.out.println("所有可行解：");dfs(0,0,rw,op,1,x);System.out.println("最少物品的解：");for(int i=1;i<w.length;i++)if(x[i]==1)System.out.print(w[i]+" ");}public static void dfs(int num,int tw,int rw,int op[],int i,int x[]){if(i>n){if(tw<=W&&num<minnum){maxw=tw;minnum=num;for(int j=1;j<=n;j++)  x[j]=op[j];}for(int j=1;j<=n;j++)    if(op[j]==1)System.out.print(w[j]+" ");System.out.println(" ");}else{op[i]=1;                             //優(yōu)先左分枝if(tw+w[i]<=W)                       //左分枝條件dfs(num+1,tw+w[i],rw-w[i],op,i+1,x);op[i]=0;if(tw+rw-w[i]>=W)dfs(num,tw,rw-w[i],op,i+1,x);}}
}

子集樹(shù)如下：（右樹(shù)部分省略）

三、復(fù)雜裝載問(wèn)題?

1、算法設(shè)計(jì)

? ? ? ? 復(fù)雜裝載問(wèn)題：n個(gè)集裝箱要裝進(jìn)兩艘載重量分別為c1和c2的輪船，其中集裝箱的重量為,不考慮集裝箱體積，設(shè)計(jì)一個(gè)算法，使得這些集裝箱裝上這兩艘輪船，如果不能裝載則返回load false。

? ? ? ? 算法：回溯法，子集樹(shù)算法，優(yōu)先第一個(gè)輪船裝載，判斷第二個(gè)輪船是否能夠裝載剩余集裝箱。

? ? ? ? dfs策略：

（1）先判斷是否為葉子結(jié)點(diǎn)，若是則判斷該解是否為最優(yōu)解，若是最優(yōu)解則把op數(shù)組存入x數(shù)組。最優(yōu)解條件：當(dāng)前選擇的集裝箱和是否大于第一個(gè)輪船的最優(yōu)集裝箱裝載重量，且選擇的集裝箱和小于第一個(gè)輪船限額

（2）若不是葉子結(jié)點(diǎn)則進(jìn)行擴(kuò)展操作。

（3）先進(jìn)行左擴(kuò)展，若tw+w[i]<=c1，即加入這個(gè)物品后，總重量不大于第一個(gè)輪船限額，則繼續(xù)擴(kuò)展，否則剪枝。

（4）再進(jìn)行右擴(kuò)展，若tw+rw-w[i]>=maxw，即不加入這個(gè)物品時(shí)，所選集裝箱總重和未選集裝箱總重的和仍然不小于第一個(gè)輪船的最優(yōu)裝載重量和，則繼續(xù)擴(kuò)展，否則剪枝。

2、代碼

//回溯法復(fù)雜裝載問(wèn)題
public class complexbestload {static int n=3;static int minnum=9999;static int c1=50;      //w為每個(gè)箱子重量static int c2=50;static int maxw=0;    //存放最優(yōu)解總重量static int w[]={0,10,40,40};public static void main(String []args){int rw=0;                    //rw為剩余集裝箱重量和for(int num:w)rw+=num;int op[]=new int[w.length];  //存放一個(gè)箱子是否裝載int x[]=new int[w.length];dfs(0,0,rw,op,1,x);judge(x);}public static void dfs(int num,int tw,int rw,int op[],int i,int x[]){if(i>n)   //dfs搜索到最后一層，所有的貨物都試了一遍，則輸出最優(yōu)解{if(tw<=c1&&tw>maxw){maxw=tw;for(int j=1;j<=n;j++)x[j]=op[j];}}else{op[i]=1;                              //優(yōu)先左分枝if(tw+w[i]<=c1)                       //左分枝條件dfs(num+1,tw+w[i],rw-w[i],op,i+1,x);op[i]=0;if(tw+rw-w[i]>=maxw)dfs(num,tw,rw-w[i],op,i+1,x);}}public static void judge(int x[]){int total=0;for(int i=1;i<w.length;i++)if(x[i]==0)total+=w[i];if(total<=c2){System.out.print("c1:");for(int i=1;i<w.length;i++)if(x[i]==1)System.out.print(w[i]+" ");System.out.println();System.out.print("c2:");for(int i=1;i<w.length;i++)if(x[i]==0)System.out.print(w[i]+" ");}   else    System.out.println("load false");}
}

四、0-1背包問(wèn)題

1、算法設(shè)計(jì)

? ? ? ? 0-1背包問(wèn)題：給定n個(gè)物品和一個(gè)背包，物品重量為，價(jià)值為，背包容量為c，請(qǐng)?jiān)O(shè)計(jì)一種算法，放入若干物品后，背包中物品總價(jià)值最大。

? ? ? ? 算法：回溯法，子集樹(shù)算法。左剪枝結(jié)合貪心算法。

? ? ? ? 初始化：首先對(duì)w數(shù)組和v數(shù)組進(jìn)行重新排序，按照a數(shù)組，即單位重量?jī)r(jià)值最高的優(yōu)先。下面代碼使用快速排序。

? ? ? ? dfs策略：

（1）先判斷是否為葉子結(jié)點(diǎn)，若是則判斷該解是否為最優(yōu)解，若是最優(yōu)解則把op數(shù)組存入x數(shù)組，最優(yōu)解maxv替換為當(dāng)前所選物品的總重量。最優(yōu)解條件：當(dāng)前所選物品總重量不大于背包限額，且所選物品的價(jià)值大于當(dāng)前最優(yōu)解maxv。

（2）若不是葉子結(jié)點(diǎn)則進(jìn)行擴(kuò)展操作。

（3）先進(jìn)行左擴(kuò)展，計(jì)算左分枝后，使用貪心算法計(jì)算已選物品與若干剩余物品，在背包未超重情況下的最大價(jià)值。若greed>maxv該最大價(jià)值已經(jīng)大于當(dāng)前已知最優(yōu)解maxv且tw+w[i]<=W當(dāng)前已選物品的總重量加上新物品仍然不大于背包限額，則進(jìn)行擴(kuò)展，否則剪枝。

（4）再進(jìn)行右擴(kuò)展，若tw+rw-w[i]>=maxw，即不加入這個(gè)物品時(shí)，所選物品總重和剩余物品總重的和仍然不小于背包限額，則繼續(xù)擴(kuò)展，否則剪枝。

2、代碼

//回溯法解決0-1背包問(wèn)題
public class backage {static int W=10;static int maxv=0;    //存放最優(yōu)解價(jià)值public static void main(String[] args){double w[]={0,2,1,3,4,6};double v[]={0,3,2,4,5,8};int n=w.length-1;double rw=0;double a[]=new double[w.length];int op[]=new int[w.length];         //存放當(dāng)前葉子結(jié)點(diǎn)的解int x[]=new int[w.length];          //存放最優(yōu)解for(int i=1;i<w.length;i++)a[i]=v[i]/w[i];for(int i=1;i<w.length;i++)rw+=w[i];//快排quickSort(a, w, v, 1, n);//回溯dfs(w,v,0,0,rw,op,x,1);int total=0;for(int j=1;j<w.length;j++){if(x[j]==1){    System.out.print(w[j]+" ");total+=v[j];}}System.out.println();System.out.println("Max value:"+total);}//快速排序public static void quickSort(double arr[],double w[],double v[],int low,int high){int i=low;int j=high;int t;if(low>high)return;double tmp=arr[low];while(i<j){while(i<j&&tmp>=arr[j]){j--;};    //注意由于降序排列，所以為tmp>=arr[j]while(i<j&&tmp<=arr[i]){i++;};    //同理，tmp<=arr[i]if(i<j){swap(arr,i,j);swap(w, i, j);swap(v,i,j);}}swap(arr,low,i);swap(w,low,i);swap(v,low,i);quickSort(arr, w,v,low, j-1);quickSort(arr,w,v,j+1,high);}//交換同一數(shù)組的兩個(gè)值public static void swap(double arr[],int i,int j){double t;t=arr[i];arr[i]=arr[j];arr[j]=t;}//回溯法public static void dfs(double w[],double v[],int num,double tw, double rw, int op[],int x[],int i){if(i>w.length-1){if(tw<=W){int tot=0;for(int j=1;j<w.length;j++){if(op[j]==1){tot+=v[j];}}if(tot>maxv){for(int j=1;j<w.length;j++)x[j]=op[j];maxv=tot;}}}else{op[i]=1;                                //優(yōu)先左分枝double greed=greedy(op, v, w, i);if(tw+w[i]<=W&&greed>maxv)                       //左分枝條件dfs(w,v,num+1,tw+w[i],rw-w[i],op,x,i+1);op[i]=0;if(tw+rw-w[i]>=W)dfs(w,v,num,tw,rw-w[i],op,x,i+1);}}//左剪枝貪心計(jì)算public static double greedy(int op[],double v[],double w[],int i){double totv=0;double totw=0;for(int j=1;j<=i;j++){if(op[j]==1){   totv+=v[j];totw+=w[j];}}for(int j=i+1;j<w.length;j++){if(totw+w[j]<W){totw+=w[j];totv+=v[j];}else{totv+=(W-totw)*v[j]/w[j];totw=W;break;}}return totv;}
}