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

问题描述 有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且 装载问题要求确定是否有一个合理的装载可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。  容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。  (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。  1、队列式分支限界法求解 在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。 活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。 节点的左子树示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r   2. using namespace std;   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. T Top() const;   13. T Last() const;   14. Queue& Add(const T& x);   15. Queue& AddLeft(const T& x);   16. Queue& Delete(T &x);   17. void Output(ostream& out)const;   18. int Length(){return (rear-front);}   19. private:   20. int front;   21. int rear;   22. int MaxSize;   23. T *queue;   24. };   25. 26. template   27. Queue::Queue(int MaxQueueSize)   28. {   29. MaxSize=MaxQueueSize+1;   30. queue=new T[MaxSize];   31. front=rear=0;   32. }   33. 34. template   35. T Queue::Top()const   36. {   37. if(IsEmpty())   38. {   39. cout<<"queue:no element,no!"<   46. T Queue ::Last()const   47. {   48. if(IsEmpty())   49. {   50. cout<<"queue:no element"<   57. Queue&  Queue::Add(const T& x)   58. {   59. if(IsFull())cout<<"queue:no memory"<   69. Queue&  Queue::AddLeft(const T& x)   70. {   71. if(IsFull())cout<<"queue:no memory"<   81. Queue&  Queue ::Delete(T & x)   82. {   83. if(IsEmpty())cout<<"queue:no element(delete)"<   94. void Queue ::Output(ostream& out)const   95. {   96. for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i--)   97. out<   101. ostream& operator << (ostream& out,const Queue& x)   102. {x.Output(out);return out;}   2、6d3-1.cpp [cpp] view plain copy 1. //装载问题 队列式分支限界法求解    2. #include "stdafx.h"   3. #include "Queue.h"   4. #include    5. using namespace std;   6. 7. const int N = 4;   8. 9. template   10. class QNode   11. {   12. template   13. friend void EnQueue(Queue*>&Q,Type wt,int i,int n,Type bestw,QNode*E,QNode *&bestE,int bestx[],bool ch);   14. 15. template   16. friend Type MaxLoading(Type w[],Type c,int n,int bestx[]);   17. 18. private:   19. QNode *parent;  //指向父节点的指针   20. bool LChild;    //左儿子标识   21. Type weight;    //节点所相应的载重量   22. };   23. 24. template   25. void EnQueue(Queue*>&Q,Type wt,int i,int n,Type bestw,QNode*E,QNode *&bestE,int bestx[],bool ch);   26. 27. template   28. Type MaxLoading(Type w[],Type c,int n,int bestx[]);   29. 30. int main()   31. {   32. float c = 70;     33. float w[] = {0,20,10,26,15};//下标从1开始     34. int x[N+1];     35. float bestw;   36. 37. cout<<"轮船载重为："<