0034算法笔记——【分支限界法】最优装载问题

《0034算法笔记——【分支限界法】最优装载问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、问题描述     有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。    容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。    (1)首先将第一艘轮船尽可能装满；   (2)将剩余的集装箱装上第二艘轮船。    1、队列式分支限界法求解    在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(

2、右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。   活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。   节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r

3、最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。   为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。   找到最优值后，可以根据parent回溯到根节点，找到最优解。   算法具体代码实现如下：   1、Queue.h[cpp] viewplain copy1.#include  2.using namespace std; 

4、 3.  4.template   5.class Queue  6.{  7.    public:  8.        Queue(int MaxQueueSize=50);  9.        ~Queue(){delete [] queue;}  10.        bool IsEmpty()const{return front==rear;}  11.        bool IsFull(){return ( (  (rear+1)  %MaxSize==front )?1:0);}  12. 

5、       T Top() const;  13.        T Last() const;  14.        Queue& Add(const T& x);  1.        Queue& AddLeft(const T& x);  2.        Queue& Delete(T &x);  3.        void Output(ostream& out)const;  4.        int Length(){return (rear-front);}  5.    private

6、:  6.        int front;  7.        int rear;  8.        int MaxSize;  9.        T *queue;  10.};  11.  12.template  13.Queue::Queue(int MaxQueueSize)  14.{  15.    MaxSize=MaxQueueSize+1;  16.    queue=new T[MaxSize];  17.    front=rear=0;  18.}  19.  20.te

7、mplate  21.T Queue::Top()const  22.{  23.    if(IsEmpty())  24.    {  25.        cout<<"queue:no element,no!"<  32.T Queue ::Last()con

8、st  33.{  34.    if(IsEmpty())  35.    {  36.        cout<<"queue:no element"<