装载问题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测试截图35一问题定义有一批共有 n 个集装箱要装上两艘载重量分别为 c1 和 c2 的

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

3、.2代码1.2-1/MaxHeap.htemplate<class T>  class MaxHeap        public:          MaxHeap(int MaxHeapSize = 10);          Max

4、Heap() delete  heap;          int Size() const return CurrentSize;          T Max()             

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

6、60;        throw OutOfBounds();                          return heap1;        &#

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

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

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

10、axSize = MaxHeapSize;      heap = new TMaxSize+1;      CurrentSize = 0;      template<class T>  MaxHeap<T>& MaxHeap<T>:Insert(const&#

11、160;T& x)  / Insert x into the max heap.      if (CurrentSize = MaxSize)                cout<<"no space!"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、#160;sibling              if (c < CurrentSize && heapc < heapc+1)                   &#

31、160;            c+;                            / can we put y in heapc

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

33、  break;  / yes                              / no            

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

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

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

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

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

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

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

41、ap<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、60;   friend class AdjacencyGraph;        private:          bbnode *parent;     /指向父节点的指针          bool&#

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

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

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

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

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

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

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

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

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

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

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

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

55、0;           /初始化      int i = 1;/当前扩展节点所处的层      bbnode *E = 0;/当前扩展节点      Type Ew = 0; /扩展节点所相应的载重量

56、60;       /搜索子集空间树      while(i!=n+1)/非叶子节点                /检查当前扩展节点的儿子节点          if(Ew+wi<=c) &

57、#160;                      AddLiveNode(H,E,Ew+wi+ri,true,i+1);                    /右儿子节点&#

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

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

60、;              /构造当前最优解      for(int j=n; j>0; j-)                bestxj = E->LChild;

61、0;         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 Queue 

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

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

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

67、#160;       Queue<T>& Delete(T &x);          void Output(ostream& out)const;          int Length()return (rear-front)

68、;      private:          int front;          int rear;          int MaxSize;     

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

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

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

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

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

74、t;T>:Add(const T& x)        if(IsFull()cout<<"queue:no memory"<<endl;      else                rear=(rear+

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

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

77、axSize-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、160;    front=(front+1) % MaxSize;          x=queuefront;            return *this;        template<class T&

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

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

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

83、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、   template<class Type>      friend Type MaxLoading(Type w,Type c,int n,int bestx);        private:          QNode *par

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

86、0;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 MaxLoading

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

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

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

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

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

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

93、;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、0;             if(wt = bestw)                        /当前最优装载重量       &

95、#160;      bestE = E;              bestxn = ch;                      &

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

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

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

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

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

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

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

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

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

105、;          if(wt>bestw)                                bestw = wt;  

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

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

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

109、0;          if(Q.IsEmpty()                                break;    &#

110、160;                       Q.Add(0);       /同层节点尾部标识              Q.Delete(E);&#

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

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

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

114、#160;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、160;         int n=3,m;      int c=50,c2=50;      int w4=0,10,40,40;      int bestx4;        m=MaxLoading

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

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

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

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

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

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

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

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

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

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

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

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

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

130、0;         bestxj=xj;                bestw=cw;                    else/进入右子

131、树                                  r-=wi;              xi=0;

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

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

134、160;         r+=wi;                  i-;                     

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

136、60;         delete x;                  return bestw;                 &

137、#160;          xi=0;              cw-=wi;              i+;        

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

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

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

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

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

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

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

145、160;      int n=3,m;      int c=50,c2=50;        int w4=0,10,40,40;      int bestx4;        m=MaxLoading(w,

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

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

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

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

150、60;      cout<<endl;        int m2=0;      for (int j=1;j<=n;j+)                m2=m2+wj*(1-best

151、xj);            cout<<"m(2)="<<m2<<endl;        if(m2>c2)                cout<<&quo

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