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)/ 到達葉結點