問(wèn)題描述：

　　有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量是wi，且不能超。

算法思想：

　　最優(yōu)裝載方案： 將第一艘輪船盡可能的裝滿；　　然后將剩余的裝載第二艘船上

算法描述：

template <class Type> class Loading {friend Type MaxLoading(Type [],Type,int);private:void Backtrack(int i);int n;Type * w,c,cw,bestw; }; template <class Type> void Loading<Type>::Backtrack(int i) {if(i>n){if(cw>bestw)bestw = cw;return;}if(cw+w[i] <= c){cw += w[i];Backtrack(i+1);cw -= w[i];}Backtrack(i+1); } template <class Type> Type MaxLoading(Type w[],Type c,int n) {Loading<Type> X;X.w = w;X.c = c;X.n = n;X.bestw = 0;X.cw = 0;X.Backtrack(1);return X.bestw; }

上界函數(shù)：

引入上界函數(shù)，用于剪去不含最優(yōu)解的子樹(shù)：

template <class Type> class Loading {friend Type MaxLoading(Type [],Type,int);private:void Backtrack(int i);int n;Type * w,c,cw,bestw,r;//剩余集裝箱重量 }; template <class Type> void Loading<Type>::Backtrack(int i) {if(i>n){if(cw>bestw)bestw = cw;return;}r-=w[i];//計(jì)算剩余的集裝箱的重量if(cw+w[i] <= c){cw += w[i];Backtrack(i+1);cw -= w[i];}Backtrack(i+1);r+=w[i];//如果得不到最優(yōu)解，再取消當(dāng)前的集裝箱，表示未選，因此剩余容量要再加上當(dāng)前集裝箱重量 } template <class Type> Type MaxLoading(Type w[],Type c,int n) {Loading<Type> X;X.w = w;X.c = c;X.n = n;X.bestw = 0;X.cw = 0;X.r = 0;for(int i=1;i<=n;i++)//計(jì)算總共的剩余集裝箱重量X.r += w[i];X.Backtrack(1);return X.bestw; }

構(gòu)造最優(yōu)解：

?　　為了構(gòu)造最優(yōu)解，必須在算法中保存最優(yōu)解的記錄。因此需要兩個(gè)成員數(shù)組 x ,bestx，一個(gè)用于記錄當(dāng)前的選擇，一個(gè)用于記錄最優(yōu)記錄。

改進(jìn)后的算法描述如下：

template <class Type> class Loading {friend Type MaxLoading(Type [],Type,int);private:void Backtrack(int i);int n,* x,* bestx;Type * w,c,cw,bestw,r;//剩余集裝箱重量 }; template <class Type> void Loading<Type>::Backtrack(int i) {if(i>n){if(cw>bestw){for(j=1;j<=n;j++)bestx[j] = x[j];bestw = cw;}return;}r-=w[i];//計(jì)算剩余的集裝箱的重量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];//如果得不到最優(yōu)解，再取消當(dāng)前的集裝箱，表示未選，因此剩余容量要再加上當(dāng)前集裝箱重量 } template <class Type> Type MaxLoading(Type w[],Type c,int n) {Loading<Type> X;X.w = w;X.c = c;X.n = n;X.bestx = bestx;X.bestw = 0;X.cw = 0;X.r = 0;for(int i=1;i<=n;i++)//計(jì)算總共的剩余集裝箱重量X.r += w[i];X.Backtrack(1);delete []X,x;return X.bestw; }

迭代回溯方式：

利用數(shù)組x所含的信息，可將上面方法表示成非遞歸的形式。省去O(n)遞歸棧空間。

template <class Type> Type MaxLoading(Type w[],Type c,int n,int bestx[]) {//迭代回溯法，返回最優(yōu)裝載量及其相應(yīng)解，初始化根節(jié)點(diǎn)int i =1;int *x = new int[n+1];Type bestw = 0,cw = 0,r = 0;for(int j=1;j<=n;j++)r+=w[j];while(true){while(i<=n && cw+w[i]<=c){r -= w[i];cw +=w[i];x[i] =1;i++;}if(i>n){for(int j=1;j<=n;j++)bestx[j] = x[j];bestw = cw;}else{r -= w[i];x[i] = 0;i++;}while(cw+w[i] <= bestw){i--;while(i>0 && !x[i]){r+=w[i];i--;}if(i == 0){delete[] x;return bestw;}x[i] =0;cw -= w[i];i++;}} }

轉(zhuǎn)載于:https://www.cnblogs.com/ITXIAZAI/p/4142976.html

總結(jié)

以上是生活随笔為你收集整理的回溯法--装载问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。