算法：回溯算法之装载问题

问题描述：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且，装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。如果有，找出一种装载方案。

 例如：当n=3,c1=c2=50,且w=[10,40,40]时，则可以将集装箱1和2装到第一艘轮船上，而将集装箱3装到第二艘轮船上；如果w=[20,40,40]，则无法将这3个集装箱都装上轮船。

基本思路： 容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。由此可知，装载问题等价于以下特殊的0-1背包问题。

用回溯法设计解装载问题的O(2^n)计算时间算法。在某些情况下该算法优于动态规划算法。

算法设计：用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。用可行性约束函数可剪去不满足约束条件

的子树。在子集树的第j+1层的结点z处，用cw记当前的装载重量，即cw=

，则当cw>c1时，以结点z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。（该约束函数去除不可行解，得到所有可行解）。

 可以引入一个上界函数，用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率。设z是解空间树第i层上的当前扩展结点。cw是当前载重量；bestw是当前最优载重量；r是剩余集装箱的重量，即r=

定义上界函数为cw+r。在以z为根的子树中任一叶结点所相应的载重量均不超过cw+r。因此，当cw+r<=bestw时，可将z的右子树剪去。
源代码：

#include
using namespace std;int bestx[4];template<class Type>
class Loading
{Type MaxLoading(Type[],Type,int);public:void Backtrack(int i);int n;//集装箱数 Type* w,//集装箱重量数组c,//第一艘轮船的载重量cw,//当前载重量bestw,//当前最优载重量 r;//剩余集装箱重量 
};template<class Type>
void Loading<Type>::Backtrack(int i)
{//搜索第i层结点 if(i>n)//到达叶节点 {if(cw>bestw)bestw=cw;//更新最优解 return;}r-=w[i];//修改剩余集装箱重量 if(cw+w[i]<=c)//x[i]=1 左儿子结点 {cw+=w[i];//装入 bestx[i]=1;Backtrack(i+1);cw-=w[i];//回溯 }if(cw+r>bestw)//x[i]=0{Backtrack(i+1);bestx[i]=0;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];}//初始时的r为全体物品重量和 X.Backtrack(1);//从第一层开始搜索 return X.bestw;
}int main()
{   int n=3,m;int c=50,c2=50;int w[4]={0,10,40,40};m=MaxLoading(w, c, n);cout<<"轮船的载重量分别为："<<endl;cout<<"c(1)="<<c<<",c(2)="<<c2<<endl;cout<<"待装集装箱重量分别为："<<endl;cout<<"w(i)=";for (int i=1;i<=n;i++){cout<<w[i]<<" ";}cout<<endl;cout<<"回溯选择结果为："<<endl;cout<<m<<endl;for(int i=1;i<=n;i++){cout<<"x["<<i<<"]:"<<bestx[i]<<endl;} return 0;
}

子集树

运行效果：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！