首页 > 代码库 > 回溯法--装载问题
回溯法--装载问题
问题描述：
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量是wi，且不能超。
算法思想：
最优装载方案： 将第一艘轮船尽可能的装满； 然后将剩余的装载第二艘船上
算法描述：
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;}上界函数：
引入上界函数，用于剪去不含最优解的子树：
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];//计算剩余的集装箱的重量 if(cw+w[i] <= c) { cw += w[i]; Backtrack(i+1); cw -= w[i]; } Backtrack(i+1); r+=w[i];//如果得不到最优解，再取消当前的集装箱，表示未选，因此剩余容量要再加上当前集装箱重量}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++)//计算总共的剩余集装箱重量 X.r += w[i]; X.Backtrack(1); return X.bestw;}构造最优解：
为了构造最优解，必须在算法中保存最优解的记录。因此需要两个成员数组 x ,bestx，一个用于记录当前的选择，一个用于记录最优记录。
改进后的算法描述如下：
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];//计算剩余的集装箱的重量 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];//如果得不到最优解，再取消当前的集装箱，表示未选，因此剩余容量要再加上当前集装箱重量}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++)//计算总共的剩余集装箱重量 X.r += w[i]; X.Backtrack(1); delete []X,x; return X.bestw;}迭代回溯方式：
利用数组x所含的信息，可将上面方法表示成非递归的形式。省去O(n)递归栈空间。
template <class Type>Type MaxLoading(Type w[],Type c,int n,int bestx[]){ //迭代回溯法，返回最优装载量及其相应解，初始化根节点 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++; } }}回溯法--装载问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。