装载问题5种解决方案

1、算法分析与设计算法分析与设计 2016/2017(2) 实验题目 装载问题5种解法 学生姓名 学生学号 学生班级 任课教师 提交日期2017 计算机科学与技术学目录一问题定义3二解决方案31优先队列式分支限界法求解31.1算法分析31.2代码31.3运行结果132队列式分支限界法求解132.1算法分析132.2代码142.3测试截图223回朔法-迭代223.1算法分析223.2代码223.3测试截图264回朔法-递归264.1算法分析264.2代码274.3测试截图315贪心算法315.1算法分析315.2代码315.3测试截图35II一问题定义有一批共有 n 个集装箱要装上两艘载重量分别为

2、c1 和 c2 的轮船，其中集装箱 i 的重量为 wi, 且重量之和小于(c1 + c2)。装载问题要求确定是否存在一个合理的装载方案可将这 n 个集装箱装上这两艘轮船。如果有，找出一种装载方案。二解决方案1优先队列式分支限界法求解1.1算法分析活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。

3、此时可终止算法。1.2代码1.2-1/MaxHeap.htemplate<class T>  class MaxHeap        public:          MaxHeap(int MaxHeapSize = 10);         

4、 MaxHeap() delete  heap;          int Size() const return CurrentSize;          T Max()           &#

5、160;         /查找             if (CurrentSize = 0)                     

6、          throw OutOfBounds();                          return heap1;       

7、;               MaxHeap<T>& Insert(const T& x); /增          MaxHeap<T>& DeleteMax(T& x);   /删 

8、60;          void Initialize(T a, int size, int ArraySize);        private:          int CurrentSize, MaxSize; 

9、0;        T *heap;  / element array      template<class T>  MaxHeap<T>:MaxHeap(int MaxHeapSize)  / Max heap constructor.    

10、0; MaxSize = MaxHeapSize;      heap = new TMaxSize+1;      CurrentSize = 0;      template<class T>  MaxHeap<T>& MaxHeap<T>:Inser

11、t(const T& x)  / Insert x into the max heap.      if (CurrentSize = MaxSize)                cout<<"no spa

12、ce!"<<endl;           return *this;               / 寻找新元素x的位置      / i初始为新叶节点的位置，逐层向上，寻找最终位置   

13、0;  int i = +CurrentSize;      while (i != 1 && x > heapi/2)                / i不是根节点，且其值大于父节点的值，需要继续调整  

14、        heapi = heapi/2; / 父节点下降          i /= 2;              / 继续向上，搜寻正确位置     

15、;        heapi = x;     return *this;      template<class T>  MaxHeap<T>& MaxHeap<T>:DeleteMax(T& x)  / Set x to&#

16、160;max element and delete max element from heap.      / check if heap is empty      if (CurrentSize = 0)          

17、      cout<<"Empty heap!"<<endl;           return *this;               x = heap1; / 删除最大

18、元素      / 重整堆      T y = heapCurrentSize-; / 取最后一个节点，从根开始重整        / find place for y starting at root     

19、60;int i = 1,  / current node of heap         ci = 2; / child of i        while (ci <= CurrentSize)    

20、;             / 使ci指向i的两个孩子中较大者          if (ci < CurrentSize && heapci < heapci+1)        

21、                ci+;                    / y的值大于等于孩子节点吗？          

22、if (y >= heapci)                        break;   / 是，i就是y的正确位置，退出             

23、;         / 否，需要继续向下，重整堆          heapi = heapci; / 大于父节点的孩子节点上升          i = ci;      

24、60;      / 向下一层，继续搜索正确位置          ci *= 2;              heapi = y;      return *this; 

25、;     template<class T>  void MaxHeap<T>:Initialize(T a, int size,int ArraySize)  / Initialize max heap to array a.      delete  heap; 

26、60;    heap = a;      CurrentSize = size;      MaxSize = ArraySize;        / 从最后一个内部节点开始，一直到根，对每个子树进行堆重整     for (i

27、nt i = CurrentSize/2; i >= 1; i-)               T y = heapi; / 子树根节点元素          / find place to&#

28、160;put y          int c = 2*i; / parent of c is target                     / location

29、0;for y          while (c <= CurrentSize)                         / heapc should be

30、0;larger sibling              if (c < CurrentSize && heapc < heapc+1)                  

31、;              c+;                            / can we put y in&#

32、160;heapc/2?              if (y >= heapc)                            

33、60;   break;  / yes                              / no          &#

34、160;   heapc/2 = heapc; / move child up              c *= 2; / move down a level           

35、0;        heapc/2 = y;          1.2-2/6d3-2.cpp/装载问题 优先队列式分支限界法求解   #include "stdafx.h"  #include "MaxHeap.h"  #include <i

36、ostream>  using namespace std;    const int N = 4;    class bbnode;    template<class Type>  class HeapNode        template<

37、;class Type>      friend void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);      template<class Type>      frie

38、nd Type MaxLoading(Type w,Type c,int n,int bestx);      public:          operator Type() constreturn uweight;      private:   

39、0;      bbnode *ptr;        /指向活节点在子集树中相应节点的指针          Type uweight;       /活节点优先级(上界)        

40、  int level;          /活节点在子集树中所处的层序号      class bbnode        template<class Type>      friend void AddLiveN

41、ode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);      template<class Type>      friend Type MaxLoading(Type w,Type c,int n,int bestx); 

42、     friend class AdjacencyGraph;        private:          bbnode *parent;     /指向父节点的指针         

43、60;bool LChild;        /左儿子节点标识      template<class Type>  void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev);   &#

44、160;template<class Type>  Type MaxLoading(Type w,Type c,int n,int bestx);      int main()        float c = 70;        float&

45、#160;w = 0,20,10,26,15;/下标从1开始        int xN+1;        float bestw;          cout<<"轮船载重为："<<c<<endl;   

46、60;    cout<<"待装物品的重量分别为："<<endl;        for(int i=1; i<=N; i+)                    cout<<wi<

47、;<" "                cout<<endl;        bestw = MaxLoading(w,c,N,x);            cout&l

48、t;<"分支限界选择结果为:"<<endl;        for(int i=1; i<=4; i+)                    cout<<xi<<" "  

49、;              cout<<endl;        cout<<"最优装载重量为："<<bestw<<endl;          return 0;   

50、    /将活节点加入到表示活节点优先队列的最大堆H中  template<class Type>  void AddLiveNode(MaxHeap<HeapNode<Type>>& H,bbnode *E,Type wt,bool ch,int lev)        bbnode *b = 

51、;new bbnode;      b->parent = E;      b->LChild = ch;      HeapNode<Type> N;        N.uweight = wt;   &

52、#160;  N.level = lev;      N.ptr = b;      H.Insert(N);      /优先队列式分支限界法，返回最优载重量，bestx返回最优解  template<class Type>  Type MaxLoading(Type w,T

53、ype c,int n,int bestx)        /定义最大的容量为1000      MaxHeap<HeapNode<Type>> H(1000);        /定义剩余容量数组      Type *r = 

54、;new Typen+1;      rn = 0;        for(int j=n-1; j>0; j-)                rj = rj+1 + wj+1; &

55、#160;            /初始化      int i = 1;/当前扩展节点所处的层      bbnode *E = 0;/当前扩展节点      Type Ew = 0; /扩展节点所

56、相应的载重量        /搜索子集空间树      while(i!=n+1)/非叶子节点                /检查当前扩展节点的儿子节点          if(Ew+wi<=

57、c)                        AddLiveNode(H,E,Ew+wi+ri,true,i+1);                    

58、;/右儿子节点          AddLiveNode(H,E,Ew+ri,false,i+1);            /取下一扩展节点          HeapNode<Type> N;     &#

59、160;    H.DeleteMax(N);/非空          i = N.level;          E = N.ptr;          Ew = N.uweight -&

60、#160;ri-1;              /构造当前最优解      for(int j=n; j>0; j-)                bestxj = E->LC

61、hild;          E = E->parent;              return Ew;    1.3运行结果2队列式分支限界法求解2.1算法分析在算法的循环体中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入

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

63、成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。找到最优值后，可以根据parent回溯到根节点，找到最优解。2.2代码22-1/Queue.h#include<iostream>  using namespace std;  template <class T>  class Qu

64、eue        public:          Queue(int MaxQueueSize=50);          Queue()delete  queue;          

65、;bool IsEmpty()constreturn front=rear;          bool IsFull()return ( (  (rear+1)%MaxSize=front )?1:0);          T Top() const;    

66、;      T Last() const;          Queue<T>& Add(const T& x);          Queue<T>& AddLeft(const T& x);

67、0;         Queue<T>& Delete(T &x);          void Output(ostream& out)const;          int Length()return (re

68、ar-front);      private:          int front;          int rear;          int MaxSize;   &#

69、160;      T *queue;      template<class T>  Queue<T>:Queue(int MaxQueueSize)        MaxSize=MaxQueueSize+1;      queue=new TMaxS

70、ize;      front=rear=0;      template<class T >  T Queue<T>:Top()const        if(IsEmpty()            &

71、#160;   cout<<"queue:no element,no!"<<endl;          return 0;            else return queue(front+1) % MaxSize;  

72、    template<class T>  T Queue<T> :Last()const        if(IsEmpty()                cout<<"queue:no element&q

73、uot;<<endl;          return 0;            else return queuerear;      template<class T>  Queue<T>& 

74、0;Queue<T>:Add(const T& x)        if(IsFull()cout<<"queue:no memory"<<endl;      else                re

75、ar=(rear+1)% MaxSize;          queuerear=x;            return *this;      template<class T>  Queue<T>&  Queue

76、<T>:AddLeft(const T& x)        if(IsFull()cout<<"queue:no memory"<<endl;      else                front

77、=(front+MaxSize-1)% MaxSize;          queue(front+1)% MaxSize=x;            return *this;      template<class T>  Queue<T

78、>&  Queue<T> :Delete(T & x)        if(IsEmpty()cout<<"queue:no element(delete)"<<endl;      else           

79、;      front=(front+1) % MaxSize;          x=queuefront;            return *this;        template<clas

80、s T>  void Queue <T>:Output(ostream& out)const        for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i-)         out<<queuei;      

81、template<class T>  ostream& operator << (ostream& out,const Queue<T>& x)  x.Output(out);return out;  2.2-2/6d3-1.cpp/装载问题 队列式分支限界法求解   #include "stdafx.h"  

82、;#include "Queue.h"  #include <iostream>  using namespace std;    const int N = 4;    template<class Type>  class QNode      

83、60; template<class Type>      friend void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx,bool ch);   

84、60;    template<class Type>      friend Type MaxLoading(Type w,Type c,int n,int bestx);        private:          QNode&

85、#160;*parent;  /指向父节点的指针          bool LChild;    /左儿子标识          Type weight;    /节点所相应的载重量      template<

86、class Type>  void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx,bool ch);    template<class Type>  Type M

87、axLoading(Type w,Type c,int n,int bestx);    int main()        float c = 70;        float w = 0,20,10,26,15;/下标从1开始     

88、   int xN+1;        float bestw;          cout<<"轮船载重为："<<c<<endl;        cout<<"待装物品的重量分别为："<<

89、endl;        for(int i=1; i<=N; i+)                    cout<<wi<<" "        

90、;        cout<<endl;        bestw = MaxLoading(w,c,N,x);            cout<<"分支限界选择结果为:"<<endl;     

91、;   for(int i=1; i<=4; i+)                    cout<<xi<<" "             

92、60;  cout<<endl;        cout<<"最优装载重量为："<<bestw<<endl;          return 0;        /将活节点加入到活节点队列Q中  template<c

93、lass Type>  void EnQueue(Queue<QNode<Type>*>&Q,Type wt,int i,int n,Type bestw,QNode<Type>*E,QNode<Type> *&bestE,int bestx,bool ch)        if(i = n)/可行叶节点 &

94、#160;              if(wt = bestw)                        /当前最优装载重量     

95、0;        bestE = E;              bestxn = ch;                    

96、0;         return;            /非叶节点      QNode<Type> *b;      b = new QNode<Type>   

97、0;  b->weight = wt;      b->parent = E;      b->LChild = ch;      Q.Add(b);      template<class Type>  Type

98、60;MaxLoading(Type w,Type c,int n,int bestx)  /队列式分支限界法，返回最优装载重量，bestx返回最优解   /初始化      Queue<QNode<Type>*> Q;      /活节点队列      Q.Add(0);  

99、;                 /同层节点尾部标识      int i = 1;               /当前扩展节点所处的层    &#

100、160; Type Ew = 0,              /扩展节点所相应的载重量           bestw = 0,          /当前最优装载重量  

101、         r = 0;            /剩余集装箱重量      for(int j=2; j<=n; j+)            &#

102、160;   r += wj;                  QNode<Type> *E = 0,           /当前扩展节点      

103、60;           *bestE;       /当前最优扩展节点        /搜索子集空间树      while(true)           

104、0;    /检查左儿子节点          Type wt = Ew + wi;          if(wt <= c)/可行节点            &#

105、160;           if(wt>bestw)                                bestw = wt;&#

106、160;                           EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);               &

107、#160;      /检查右儿子节点          if(Ew+r>bestw)                        EnQueue(Q,Ew,i,n,bestw,E,bestE

108、,bestx,false);                    Q.Delete(E);/取下一扩展节点          if(!E)/同层节点尾部            &

109、#160;           if(Q.IsEmpty()                                break;   

110、;                         Q.Add(0);       /同层节点尾部标识              Q.Del

111、ete(E);    /取下一扩展节点              i+;            /进入下一层              r-=wi; 

112、       /剩余集装箱重量                    Ew  =E->weight;      /新扩展节点所对应的载重量         

113、;   /构造当前最优解      for(int j=n-1; j>0; j-)                bestxj = bestE->LChild;          best

114、E = bestE->parent;            return bestw;    2.3测试截图3回朔法-迭代3.1算法分析用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束条件重量之和小于(c1 + c2)可剪去不满足约束条件的子树用cw记当前的装载重量，即cw=(w1x1+w2x2+.+wjxj)，当cw>c1时，以节点Z为根的子树中所有节点都不满足约束条件，因

115、而该子树中解均为不可行解，故可将该子树剪去。3.2代码#include <iostream>  using namespace std;     template<class Type>  Type MaxLoading(Type w , Type c, int n, int bestx );  int main(

116、)           int n=3,m;      int c=50,c2=50;      int w4=0,10,40,40;      int bestx4;        m=M

117、axLoading(w, c, n, bestx);        cout<<"轮船的载重量分别为："<<endl;      cout<<"c(1)="<<c<<",c(2)="<<c2<<endl;       

118、; cout<<"待装集装箱重量分别为："<<endl;      cout<<"w(i)="      for (int i=1;i<=n;i+)                cout<<wi

119、<<" "            cout<<endl;        cout<<"回溯选择结果为："<<endl;      cout<<"m(1)="<<m<<endl; 

120、;     cout<<"x(i)="        for (int i=1;i<=n;i+)                cout<<bestxi<<" "   

121、         cout<<endl;        int m2=0;      for (int j=1;j<=n;j+)                m

122、2=m2+wj*(1-bestxj);            cout<<"m(2)="<<m2<<endl;        if(m2>c2)                &

123、#160;cout<<"因为m(2)大于c(2),所以原问题无解！"<<endl;            return 0;        template <class Type>  Type MaxLoading(Type w,Type c,int 

124、n,int bestx)/迭代回溯法，返回最优载重量及其相应解，初始化根结点        int i=1;/当前层，x1:i-1为当前路径      int *x=new intn+1;        Type bestw=0,      /当前最优载重量 

125、          cw=0,         /当前载重量           r=0;          /剩余集装箱重量      &

126、#160; for (int j=1;j<=n;j+)                r+=wj;            while(true)/搜索子树           

127、;          while(i<=n &&cw+wi<=c)/进入左子树                        r-=wi;       

128、       cw+=wi;              xi=1;              i+;            

129、60;      if (i>n)/到达叶结点                              for (int j=1;j<=n;j+)    &

130、#160;          bestxj=xj;                bestw=cw;                    

131、else/进入右子树                                  r-=wi;             &#

132、160;xi=0; i+;                    while (cw+r<=bestw)           /剪枝回溯          

133、0;   i-;                 while (i>0 && !xi)                      

134、;           r+=wi;                  i-;                   &#

135、160;           /从右子树返回              if (i=0)                     

136、           delete x;                  return bestw;               

137、0;            xi=0;              cw-=wi;              i+;       &

138、#160;               3.3测试截图4回朔法-递归4.1算法分析与回朔法-迭代的相同，以下代码只是更改了具体的实现过程4.2代码#include <iostream>  using namespace std;     template <class Type>  c

139、lass Loading        /friend Type MaxLoading(Type,Type,int,int );      /private:      public:          void Backtrack(int 

140、;i);          int n,          /集装箱数              *x,         /当前解  

141、60;           *bestx;     /当前最优解              Type *w,    /集装箱重量数组          

142、;    c,          /第一艘轮船的载重量              cw,         /当前载重量         &#

143、160;    bestw,      /当前最优载重量              r;          /剩余集装箱重量      template <class Typ

144、e>  void  Loading <Type>:Backtrack (int i);    template<class Type>  Type MaxLoading(Type w, Type c, int n, int bestx);    int main()   

145、;        int n=3,m;      int c=50,c2=50;        int w4=0,10,40,40;      int bestx4;        m=MaxLoad

146、ing(w, c, n, bestx);        cout<<"轮船的载重量分别为："<<endl;      cout<<"c(1)="<<c<<",c(2)="<<c2<<endl;        

147、;cout<<"待装集装箱重量分别为："<<endl;      cout<<"w(i)="      for (int i=1;i<=n;i+)                cout<<wi<&l

148、t;" "            cout<<endl;        cout<<"回溯选择结果为："<<endl;      cout<<"m(1)="<<m<<endl;  

149、;    cout<<"x(i)="        for (int i=1;i<=n;i+)                cout<<bestxi<<" "    

150、        cout<<endl;        int m2=0;      for (int j=1;j<=n;j+)                m2=m2+w

151、j*(1-bestxj);            cout<<"m(2)="<<m2<<endl;        if(m2>c2)                cout<

152、;<"因为m(2)大于c(2),所以原问题无解！"<<endl;            return 0;      template <class Type>  void  Loading <Type>:Backtrack (int i)/ 搜索第i层结点        if (i > n)/ 到达叶结点