裝載問(wèn)題5種解決方案

1、算法分析與設(shè)計(jì)算法分析與設(shè)計(jì) 2016/2017(2) 實(shí)驗(yàn)題目 裝載問(wèn)題5種解法 學(xué)生姓名 學(xué)生學(xué)號(hào) 學(xué)生班級(jí) 任課教師 提交日期2017 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)目錄一問(wèn)題定義3二解決方案31優(yōu)先隊(duì)列式分支限界法求解31.1算法分析31.2代碼31.3運(yùn)行結(jié)果132隊(duì)列式分支限界法求解132.1算法分析132.2代碼142.3測(cè)試截圖223回朔法-迭代223.1算法分析223.2代碼223.3測(cè)試截圖264回朔法-遞歸264.1算法分析264.2代碼274.3測(cè)試截圖315貪心算法315.1算法分析315.2代碼315.3測(cè)試截圖35II一問(wèn)題定義有一批共有 n 個(gè)集裝箱要裝上兩艘載重量分別為

2、c1 和 c2 的輪船，其中集裝箱 i 的重量為 wi, 且重量之和小于(c1 + c2)。裝載問(wèn)題要求確定是否存在一個(gè)合理的裝載方案可將這 n 個(gè)集裝箱裝上這兩艘輪船。如果有，找出一種裝載方案。二解決方案1優(yōu)先隊(duì)列式分支限界法求解1.1算法分析活結(jié)點(diǎn)x在優(yōu)先隊(duì)列中的優(yōu)先級(jí)定義為從根結(jié)點(diǎn)到結(jié)點(diǎn)x的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和。優(yōu)先隊(duì)列中優(yōu)先級(jí)最大的活結(jié)點(diǎn)成為下一個(gè)擴(kuò)展結(jié)點(diǎn)。以結(jié)點(diǎn)x為根的子樹中所有結(jié)點(diǎn)相應(yīng)的路徑的載重量不超過(guò)它的優(yōu)先級(jí)。子集樹中葉結(jié)點(diǎn)所相應(yīng)的載重量與其優(yōu)先級(jí)相同。在優(yōu)先隊(duì)列式分支限界法中，一旦有一個(gè)葉結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，則可以斷言該葉結(jié)點(diǎn)所相應(yīng)的解即為最優(yōu)解。

3、此時(shí)可終止算法。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初始為新葉節(jié)點(diǎn)的位置，逐層向上，尋找最終位置   

13、0;  int i = +CurrentSize;      while (i != 1 && x > heapi/2)                / i不是根節(jié)點(diǎn)，且其值大于父節(jié)點(diǎn)的值，需要繼續(xù)調(diào)整  

14、        heapi = heapi/2; / 父節(jié)點(diǎn)下降          i /= 2;              / 繼續(xù)向上，搜尋正確位置     

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-; / 取最后一個(gè)節(jié)點(diǎn)，從根開(kāi)始重整        / 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的兩個(gè)孩子中較大者          if (ci < CurrentSize && heapci < heapci+1)        

21、                ci+;                    / y的值大于等于孩子節(jié)點(diǎn)嗎？          

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

23、;         / 否，需要繼續(xù)向下，重整堆          heapi = heapci; / 大于父節(jié)點(diǎn)的孩子節(jié)點(diǎn)上升          i = ci;      

24、60;      / 向下一層，繼續(xù)搜索正確位置          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;        / 從最后一個(gè)內(nèi)部節(jié)點(diǎn)開(kāi)始，一直到根，對(duì)每個(gè)子樹進(jìn)行堆重整     for (i

27、nt i = CurrentSize/2; i >= 1; i-)               T y = heapi; / 子樹根節(jié)點(diǎn)元素          / 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/裝載問(wèn)題 優(yōu)先隊(duì)列式分支限界法求解   #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;        /指向活節(jié)點(diǎn)在子集樹中相應(yīng)節(jié)點(diǎn)的指針          Type uweight;       /活節(jié)點(diǎn)優(yōu)先級(jí)(上界)        

40、  int level;          /活節(jié)點(diǎn)在子集樹中所處的層序號(hào)      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;     /指向父節(jié)點(diǎn)的指針         

43、60;bool LChild;        /左兒子節(jié)點(diǎn)標(biāo)識(shí)      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;/下標(biāo)從1開(kāi)始        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;<"分支限界選擇結(jié)果為:"<<endl;        for(int i=1; i<=4; i+)                    cout<<xi<<" "  

49、;              cout<<endl;        cout<<"最優(yōu)裝載重量為："<<bestw<<endl;          return 0;   

50、    /將活節(jié)點(diǎn)加入到表示活節(jié)點(diǎn)優(yōu)先隊(duì)列的最大堆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);      /優(yōu)先隊(duì)列式分支限界法，返回最優(yōu)載重量，bestx返回最優(yōu)解  template<class Type>  Type MaxLoading(Type w,T

53、ype c,int n,int bestx)        /定義最大的容量為1000      MaxHeap<HeapNode<Type>> H(1000);        /定義剩余容量數(shù)組      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;/當(dāng)前擴(kuò)展節(jié)點(diǎn)所處的層      bbnode *E = 0;/當(dāng)前擴(kuò)展節(jié)點(diǎn)      Type Ew = 0; /擴(kuò)展節(jié)點(diǎn)所

56、相應(yīng)的載重量        /搜索子集空間樹      while(i!=n+1)/非葉子節(jié)點(diǎn)                /檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的兒子節(jié)點(diǎn)          if(Ew+wi<=

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

58、;/右兒子節(jié)點(diǎn)          AddLiveNode(H,E,Ew+ri,false,i+1);            /取下一擴(kuò)展節(jié)點(diǎn)          HeapNode<Type> N;     &#

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

60、#160;ri-1;              /構(gòu)造當(dāng)前最優(yōu)解      for(int j=n; j>0; j-)                bestxj = E->LC

61、hild;          E = E->parent;              return Ew;    1.3運(yùn)行結(jié)果2隊(duì)列式分支限界法求解2.1算法分析在算法的循環(huán)體中，首先檢測(cè)當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。如果是則將其加入到活結(jié)點(diǎn)隊(duì)列中。然后將其右兒子結(jié)點(diǎn)加入

62、到活結(jié)點(diǎn)隊(duì)列中(右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn))。2個(gè)兒子結(jié)點(diǎn)都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點(diǎn)被舍棄?；罱Y(jié)點(diǎn)隊(duì)列中的隊(duì)首元素被取出作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，由于隊(duì)列中每一層結(jié)點(diǎn)之后都有一個(gè)尾部標(biāo)記-1，故在取隊(duì)首元素時(shí)，活結(jié)點(diǎn)隊(duì)列一定不空。當(dāng)取出的元素是-1時(shí)，再判斷當(dāng)前隊(duì)列是否為空。如果隊(duì)列非空，則將尾部標(biāo)記-1加入活結(jié)點(diǎn)隊(duì)列，算法開(kāi)始處理下一層的活結(jié)點(diǎn)。節(jié)點(diǎn)的左子樹表示將此集裝箱裝上船，右子樹表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量；r是剩余集裝箱的重量。則當(dāng)ew+r<bestw時(shí)，可將其右子樹剪去，因?yàn)榇藭r(shí)若要船裝最多集裝箱，就應(yīng)該把此箱裝上船。另外，為了確保右子樹

63、成功剪枝，應(yīng)該在算法每一次進(jìn)入左子樹的時(shí)候更新bestw的值。為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法必須存儲(chǔ)相應(yīng)子集樹中從活結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。為此目的，可在每個(gè)結(jié)點(diǎn)處設(shè)置指向其父結(jié)點(diǎn)的指針，并設(shè)置左、右兒子標(biāo)志。找到最優(yōu)值后，可以根據(jù)parent回溯到根節(jié)點(diǎn)，找到最優(yōu)解。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/裝載問(wèn)題 隊(duì)列式分支限界法求解   #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;  /指向父節(jié)點(diǎn)的指針          bool LChild;    /左兒子標(biāo)識(shí)          Type weight;    /節(jié)點(diǎn)所相應(yīng)的載重量      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;/下標(biāo)從1開(kāi)始     

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<<"分支限界選擇結(jié)果為:"<<endl;     

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

92、60;  cout<<endl;        cout<<"最優(yōu)裝載重量為："<<bestw<<endl;          return 0;        /將活節(jié)點(diǎn)加入到活節(jié)點(diǎn)隊(duì)列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)/可行葉節(jié)點(diǎn) &

94、#160;              if(wt = bestw)                        /當(dāng)前最優(yōu)裝載重量     

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

96、0;         return;            /非葉節(jié)點(diǎn)      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)  /隊(duì)列式分支限界法，返回最優(yōu)裝載重量，bestx返回最優(yōu)解   /初始化      Queue<QNode<Type>*> Q;      /活節(jié)點(diǎn)隊(duì)列      Q.Add(0);  

99、;                 /同層節(jié)點(diǎn)尾部標(biāo)識(shí)      int i = 1;               /當(dāng)前擴(kuò)展節(jié)點(diǎn)所處的層    &#

100、160; Type Ew = 0,              /擴(kuò)展節(jié)點(diǎn)所相應(yīng)的載重量           bestw = 0,          /當(dāng)前最優(yōu)裝載重量  

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

102、160;   r += wj;                  QNode<Type> *E = 0,           /當(dāng)前擴(kuò)展節(jié)點(diǎn)      

103、60;           *bestE;       /當(dāng)前最優(yōu)擴(kuò)展節(jié)點(diǎn)        /搜索子集空間樹      while(true)           

104、0;    /檢查左兒子節(jié)點(diǎn)          Type wt = Ew + wi;          if(wt <= c)/可行節(jié)點(diǎn)            &#

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

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

107、#160;      /檢查右兒子節(jié)點(diǎn)          if(Ew+r>bestw)                        EnQueue(Q,Ew,i,n,bestw,E,bestE

108、,bestx,false);                    Q.Delete(E);/取下一擴(kuò)展節(jié)點(diǎn)          if(!E)/同層節(jié)點(diǎn)尾部            &

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

110、;                         Q.Add(0);       /同層節(jié)點(diǎn)尾部標(biāo)識(shí)              Q.Del

111、ete(E);    /取下一擴(kuò)展節(jié)點(diǎn)              i+;            /進(jìn)入下一層              r-=wi; 

112、       /剩余集裝箱重量                    Ew  =E->weight;      /新擴(kuò)展節(jié)點(diǎn)所對(duì)應(yīng)的載重量         

113、;   /構(gòu)造當(dāng)前最優(yōu)解      for(int j=n-1; j>0; j-)                bestxj = bestE->LChild;          best

114、E = bestE->parent;            return bestw;    2.3測(cè)試截圖3回朔法-迭代3.1算法分析用回溯法解裝載問(wèn)題時(shí)，用子集樹表示其解空間顯然是最合適的?？尚行约s束條件重量之和小于(c1 + c2)可剪去不滿足約束條件的子樹用cw記當(dāng)前的裝載重量，即cw=(w1x1+w2x2+.+wjxj)，當(dāng)cw>c1時(shí)，以節(jié)點(diǎn)Z為根的子樹中所有節(jié)點(diǎn)都不滿足約束條件，因

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<<"回溯選擇結(jié)果為："<<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<<"因?yàn)閙(2)大于c(2),所以原問(wèn)題無(wú)解！"<<endl;            return 0;        template <class Type>  Type MaxLoading(Type w,Type c,int 

124、n,int bestx)/迭代回溯法，返回最優(yōu)載重量及其相應(yīng)解，初始化根結(jié)點(diǎn)        int i=1;/當(dāng)前層，x1:i-1為當(dāng)前路徑      int *x=new intn+1;        Type bestw=0,      /當(dāng)前最優(yōu)載重量 

125、          cw=0,         /當(dāng)前載重量           r=0;          /剩余集裝箱重量      &

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

127、;          while(i<=n &&cw+wi<=c)/進(jìn)入左子樹                        r-=wi;       

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

129、60;      if (i>n)/到達(dá)葉結(jié)點(diǎn)                              for (int j=1;j<=n;j+)    &

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

131、else/進(jìn)入右子樹                                  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測(cè)試截圖4回朔法-遞歸4.1算法分析與回朔法-迭代的相同，以下代碼只是更改了具體的實(shí)現(xiàn)過(guò)程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,          /集裝箱數(shù)              *x,         /當(dāng)前解  

141、60;           *bestx;     /當(dāng)前最優(yōu)解              Type *w,    /集裝箱重量數(shù)組          

142、;    c,          /第一艘輪船的載重量              cw,         /當(dāng)前載重量         &#

143、160;    bestw,      /當(dāng)前最優(yōu)載重量              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<<"回溯選擇結(jié)果為："<<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、;<"因?yàn)閙(2)大于c(2),所以原問(wèn)題無(wú)解！"<<endl;            return 0;      template <class Type>  void  Loading <Type>:Backtrack (int i)/ 搜索第i層結(jié)點(diǎn)        if (i > n)/ 到達(dá)葉結(jié)點(diǎn)