算法分析與設(shè)計(jì)2016/2017(2)實(shí)驗(yàn)題目裝載問(wèn)題5種解法學(xué)生姓名學(xué)生學(xué)號(hào)學(xué)生班級(jí)任課教師提交日期2017計(jì)算機(jī)科學(xué)與技術(shù)學(xué)目錄TOC\o"1-5"\h\z\o"CurrentDocument"一問(wèn)題定義4\o"CurrentDocument"二解決方案41優(yōu)先隊(duì)列式分支限界法求解.41.1算法分析.4\o"CurrentDocument"1.2代碼4\o"CurrentDocument"1.3運(yùn)行結(jié)果172隊(duì)列式分支限界法求解172.1算法分析17\o"CurrentDocument"2.2代碼18\o"CurrentDocument"2.3測(cè)試截圖303回朔法-迭代303.1算法分析30\o"CurrentDocument"3.2代碼30\o"CurrentDocument"3.3測(cè)試截圖354回朔法-遞歸354.1算法分析35\o"CurrentDocument"4.2代碼35\o"CurrentDocument"4.3測(cè)試截圖415貪心算法425.1算法分析42\o"CurrentDocument"5.2代碼42\o"CurrentDocument"5.3測(cè)試截圖46一問(wèn)題定義有一批共有n個(gè)集裝箱要裝上兩艘載重量分別為cl和c2的輪船，其中集裝箱i的重量為w[i],且重量之和小于(cl+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為根的子樹(shù)中所有結(jié)點(diǎn)相應(yīng)的路徑的載重量不超過(guò)它的優(yōu)先級(jí)。子集樹(shù)中葉結(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)解。此時(shí)可終止算法。1.2代碼1〃〃MaxHeap.htemplate<classT>classMaxHeap{public:MaxHeap(intMaxHeapSize=10);~MaxHeap(){delete[]heap;}intSize()const{returnCurrentSize;}TMax(){〃查找if(CurrentSize==0){throwOutOfBounds();}returnheap[1];}MaxHeap<T>&Insert(constT&x);〃增MaxHeap<T>&DeleteMax(T&x);〃刪voidInitialize(Ta[],intsize,intArraySize);private:intCurrentSize,MaxSize;T*heap;//elementarraytemplate<classT>MaxHeap<T>::MaxHeap(intMaxHeapSize){//Maxheapconstructor.MaxSize=MaxHeapSize;heap=newT[MaxSize+1];CurrentSize=0;}template<classT>MaxHeap<T>&MaxHeap<T>::Insert(constT&x){//Insertxintothemaxheap.if(CurrentSize==MaxSize){cout<<"nospace!"<<endl;return*this;}//尋找新元素x的位置//i——初始為新葉節(jié)點(diǎn)的位置，逐層向上，尋找最終位置inti=++CurrentSize;while(i!=1&&x>heap[i/2]){//i不是根節(jié)點(diǎn)，且其值大于父節(jié)點(diǎn)的值，需要繼續(xù)調(diào)整heap[i]=heap[i/2];//父節(jié)點(diǎn)下降i/=2;//繼續(xù)向上，搜尋正確位置}heap[i]=x;return*this;}template<classT>MaxHeap<T>&MaxHeap<T>::DeleteMax(T&x){//Setxtomaxelementanddeletemaxelementfromheap.//checkifheapisemptyif(CurrentSize==0){cout<<"Emptyheap!"<<endl;return*this;}x=heap[1];//刪除最大元素//重整堆Ty=heap[CurrentSize--];//取最后一個(gè)節(jié)點(diǎn),從根開(kāi)始重整//findplaceforystartingatrootinti=1,//currentnodeofheapci=2;//childofiwhile(ci<=CurrentSize){//使ci指向i的兩個(gè)孩子中較大者if(ci<CurrentSize&&heap[ci]<heap[ci+1]){ci++;}//y的值大于等于孩子節(jié)點(diǎn)嗎？if(y>=heap[ci]){break;//是，i就是y的正確位置,退出}//否，需要繼續(xù)向下，重整堆heap[i]=heap[ci];//大于父節(jié)點(diǎn)的孩子節(jié)點(diǎn)上升i=ci;//向下一層，繼續(xù)搜索正確位置ci*二2;}heap[i]=y;return*this;}template<classT>voidMaxHeap<T>::Initialize(Ta[],intsize,intArraySize){//Initializemaxheaptoarraya.delete[]heap;heap=a;CurrentSize=size;MaxSize=ArraySize;//從最后一個(gè)內(nèi)部節(jié)點(diǎn)開(kāi)始，一直到根，對(duì)每個(gè)子樹(shù)進(jìn)行堆重整for(inti=CurrentSize/2;i>=1;i--){Ty=heap[i];//子樹(shù)根節(jié)點(diǎn)元素//findplacetoputyintc=2*i;//parentofcistarget//locationforywhile(c<=CurrentSize){//heap[c]shouldbelargersiblingif(c<CurrentSize&&heap[c]<heap[c+1]){c++;}//canweputyinheap[c/2]?if(y>=heap[c]){break;//yes}//noheap[c/2]=heap[c];//movechildupc*=2;//movedownalevel}heap[c/2]=y;}}2///6d3-2.cpp//裝載問(wèn)題優(yōu)先隊(duì)列式分支限界法求解#include"stdafx.h"#include"MaxHeap.h"#include<iostream>usingnamespacestd;constintN=4;classbbnode;template<classType>classHeapNode{template<classType>friendvoidAddLiveNode(MaxHeap<HeapNode<Type>>&H,bbnode*E,Typewt,boolch,intlev);template<classType>friendTypeMaxLoading(Typew[],Typec,intn,intbestx[]);public:operatorType()const{returnuweight;}private:bbnode*ptr;//指向活節(jié)點(diǎn)在子集樹(shù)中相應(yīng)節(jié)點(diǎn)的指針Typeuweight;//活節(jié)點(diǎn)優(yōu)先級(jí)(上界)intlevel;//活節(jié)點(diǎn)在子集樹(shù)中所處的層序號(hào)}；classbbnode{template<classType>friendvoidAddLiveNode(MaxHeap<HeapNode<Type>>&H,bbnode*E,Typewt,boolch,intlev);template<classType>friendTypeMaxLoading(Typew[],Typec,intn,intbestx[]);friendclassAdjacencyGraph;private:bbnode*parent;//指向父節(jié)點(diǎn)的指針boolLChild;//左兒子節(jié)點(diǎn)標(biāo)識(shí)};template<classType>voidAddLiveNode(MaxHeap<HeapNode<Type>>&H,bbnode*E,Typewt,boolch,intlev);TypeMaxLoading(Typew[],Typec,intn,intbestx[]);intmain(){floatc=70;floatw[]={0,20,10,26,15};//下標(biāo)從1開(kāi)始intx[N+1];floatbestw;cout<<"輪船載重為："<<c<<endl;cout<<"待裝物品的重量分別為："<<endl;for(inti=1;i<=N;i++){cout<<w[i]<<"";}cout<<endl;bestw=MaxLoading(w,c,N,x);cout<<"分支限界選擇結(jié)果為:"<<endl;for(inti=1;i<=4;i++){cout<<x[i]<<””;}cout<<endl;cout<<"最優(yōu)裝載重量為："<<bestw<<endl;return0;}//將活節(jié)點(diǎn)加入到表示活節(jié)點(diǎn)優(yōu)先隊(duì)列的最大堆H中template<classType>voidAddLiveNode(MaxHeap<HeapNode<Type>>&H,bbnode*E,Typewt,boolch,intlev){bbnode*b=newbbnode;b->parent=E;b->LChild=ch;HeapNode<Type>N;N.uweight=wt;N.level=lev;N.ptr=b;H.Insert(N);}〃優(yōu)先隊(duì)列式分支限界法,返回最優(yōu)載重量,bestx返回最優(yōu)解template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]){〃定義最大的容量為1000MaxHeap<HeapNode<Type>>H(1000);〃定義剩余容量數(shù)組Type*r=newType[n+1];r[n]=0;for(intj=n-1;j>0;j--){r[j]=r[j+1]+w[j+1];}//初始化inti=1;//當(dāng)前擴(kuò)展節(jié)點(diǎn)所處的層bbnode*E=0;//當(dāng)前擴(kuò)展節(jié)點(diǎn)TypeEw=0;〃擴(kuò)展節(jié)點(diǎn)所相應(yīng)的載重量//搜索子集空間樹(shù)while(i!=n+1)//非葉子節(jié)點(diǎn){〃檢查當(dāng)前擴(kuò)展節(jié)點(diǎn)的兒子節(jié)點(diǎn)if(Ew+w[i]<=c){AddLiveNode(H,E,Ew+w[i]+r[i],true,i+1);}//右兒子節(jié)點(diǎn)AddLiveNode(H,E,Ew+r[i],false,i+1);//取下一擴(kuò)展節(jié)點(diǎn)HeapNode<Type>N;H.DeleteMax(N);//非空i=N.level;E=N.ptr;Ew=N.uweight-r[i-1];}

〃構(gòu)造當(dāng)前最優(yōu)解for(intj=n;j>0;j--){bestx[j]=E->LChild;E=E->parent;}returnEw;}1.3運(yùn)行結(jié)果理重結(jié)母.■重5搔選重建.重品新果1菱思S0限1裝任充1最請(qǐng)2隊(duì)列式分支限界法求解2.1理重結(jié)母.■重5搔選重建.重品新果1菱思S0限1裝任充1最請(qǐng)?jiān)谒惴ǖ难h(huán)體中，首先檢測(cè)當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。如果是則將其加入到活結(jié)點(diǎn)隊(duì)列中。然后將其右兒子結(jié)點(diǎn)加入到活結(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ù)表示將此集裝箱裝上船,右子樹(shù)表示不將此集裝箱裝上船。設(shè)bestw是當(dāng)前最優(yōu)解；ew是當(dāng)前擴(kuò)展結(jié)點(diǎn)所相應(yīng)的重量;r是剩余集裝箱的重量。則當(dāng)ew+r<bestw時(shí),可將其右子樹(shù)剪去,因?yàn)榇藭r(shí)若要船裝最多集裝箱,就應(yīng)該把此箱裝上船。另外,為了確保右子樹(shù)成功剪枝,應(yīng)該在算法每一次進(jìn)入左子樹(shù)的時(shí)候更新bestw的值。為了在算法結(jié)束后能方便地構(gòu)造出與最優(yōu)值相應(yīng)的最優(yōu)解，算法必須存儲(chǔ)相應(yīng)子集樹(shù)中從活結(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>usingnamespacestd;template<classT>classQueuepublic:Queue(intMaxQueueSize=50);~Queue(){delete[]queue;}boolIsEmpty()const{returnfront二二rear;}boolIsFull(){return(((rear+1)%MaxSize二二front)?1:0);}TTop()const;TLast()const;Queue<T>&Add(constT&x);Queue<T>&AddLeft(constT&x);Queue<T>&Delete(T&x);voidOutput(ostream&out)const;intLength(){return(rear-front);}private:intfront;intrear;intMaxSize;T*queue;};template<classT>Queue<T>::Queue(intMaxQueueSize){MaxSize二MaxQueueSize+1;queue=newT[MaxSize];front=rear=0;}template<classT>TQueue<T>::Top()const{if(IsEmpty()){cout<<"queue:noelement,no!"<<endl;return0;}elsereturnqueue[(front+1)%MaxSize];}template<classT>TQueue<T>::Last()const{if(IsEmpty()){cout<<"queue:noelement"<<endl;return0;elsereturnqueue[rear];}template<classT>Queue<T>&Queue<T>::Add(constT&x){if(IsFull())cout<<"queue:nomemory"<<endl;else{rear=(rear+1)%MaxSize;queue[rear]=x;}return*this;}template<classT>Queue<T>&Queue<T>::AddLeft(constT&x){if(IsFull())cout<<"queue:nomemory"<<endl;elsefront=(front+MaxSize-1)%MaxSize;queue[(front+1)%MaxSize]=x;}return*this;}template<classT>Queue<T>&Queue<T>::Delete(T&x){if(IsEmpty())cout<<"queue:noelement(delete)"<<endl;else{front=(front+1)%MaxSize;x=queue[front];}return*this;}template<classT>voidQueue<T>::Output(ostream&out)constfor(inti二rear%MaxSize;i>=(front+1)%MaxSize;i--)out<<queue[i];}template<classT>ostream&operator<<(ostream&out,constQueue<T>&x){x.Output(out);returnout;}2////6d3-1.cpp//裝載問(wèn)題隊(duì)列式分支限界法求解#include"stdafx.h"#include"Queue.h"#include<iostream>usingnamespacestd;constintN=4;template<classType>classQNode{template<classType>friendvoidEnQueue(Queue<QNode<Type>*>&Q,Typewt,inti,intn,Typebestw,QNode<Type>*E,QNode<Type>*&bestE,intbestx[],boolch);template<classType>friendTypeMaxLoading(Typew[],Typec,intn,intbestx[]);private:QNode*parent;//指向父節(jié)點(diǎn)的指針boolLChild;//左兒子標(biāo)識(shí)Typeweight;〃節(jié)點(diǎn)所相應(yīng)的載重量};template<classType>voidEnQueue(Queue<QNode<Type>*>&Q,Typewt,inti,intn,Typebestw,QNode<Type>*E,QNode<Type>*&bestE,intbestx[],boolch);template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]);intmain(){floatc=70;floatw[]={0,20,10,26,15};//下標(biāo)從1開(kāi)始intx[N+1];floatbestw;cout<<"輪船載重為："<<c<<endl;cout<<"待裝物品的重量分別為："<<endl;for(inti=1;i<=N;i++){cout<<w[i]<<"";}cout<<endl;bestw=MaxLoading(w,c,N,x);cout<<"分支限界選擇結(jié)果為:"<<endl;for(inti=1;i<=4;i++){cout<<x[i]<<"";}cout<<endl;cout<<"最優(yōu)裝載重量為："<<bestw<<endl;return0;//將活節(jié)點(diǎn)加入到活節(jié)點(diǎn)隊(duì)列Q中template<classType>voidEnQueue(Queue<QNode<Type>*>&Q,Typewt,inti,intn,Typebestw,QNode<Type>*E,QNode<Type>*&bestE,intbestx[],boolch){if(i==門(mén))//可行葉節(jié)點(diǎn){if(wt==bestw){〃當(dāng)前最優(yōu)裝載重量bestE=E;bestx[n]=ch;}return;}〃非葉節(jié)點(diǎn)QNode<Type>*b;b=newQNode<Type>;b->weight=wt;b->parent=E;b->LChild=ch;Q.Add(b);}template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]){〃隊(duì)列式分支限界法,返回最優(yōu)裝載重量,bestx返回最優(yōu)解//初始化Queue<QNode<Type>*>Q;//活節(jié)點(diǎn)隊(duì)列Q.Add(0);//同層節(jié)點(diǎn)尾部標(biāo)識(shí)inti=1;〃當(dāng)前擴(kuò)展節(jié)點(diǎn)所處的層TypeEw=0,//擴(kuò)展節(jié)點(diǎn)所相應(yīng)的載重量bestw=0,〃當(dāng)前最優(yōu)裝載重量r=0;//剩余集裝箱重量for(intj=2;j<=n;j++){r+=w[j];}QNode<Type>*E=0,//當(dāng)前擴(kuò)展節(jié)點(diǎn)*bestE;〃當(dāng)前最優(yōu)擴(kuò)展節(jié)點(diǎn)//搜索子集空間樹(shù)while(true){〃檢查左兒子節(jié)點(diǎn)Typewt=Ew+w[i];if(wt<=c)//可行節(jié)點(diǎn){if(wt>bestw){bestw=wt;}EnQueue(Q,wt,i,n,bestw,E,bestE,bestx,true);}〃檢查右兒子節(jié)點(diǎn)if(Ew+r>bestw){EnQueue(Q,Ew,i,n,bestw,E,bestE,bestx,false);}Q.Delete(E);//取下一擴(kuò)展節(jié)點(diǎn)if(!E)〃同層節(jié)點(diǎn)尾部{if(Q.IsEmpty())break;}Q.Add(0);//同層節(jié)點(diǎn)尾部標(biāo)識(shí)Q.Delete(E);//取下一擴(kuò)展節(jié)點(diǎn)i++;〃進(jìn)入下一層r-=w[i];//剩余集裝箱重量}Ew=E->weight;//新擴(kuò)展節(jié)點(diǎn)所對(duì)應(yīng)的載重量}〃構(gòu)造當(dāng)前最優(yōu)解for(intj=n-1;j>0;j--){bestx[j]=bestE->LChild;bestE=bestE->parent;}returnbestw;}2.3測(cè)試截圖暮麝勰鑫分別為2$2615分支限界選擇結(jié)果為<3回朔法■迭代3.1算法分析用回溯法解裝載問(wèn)題時(shí)，用子集樹(shù)表示其解空間顯然是最合適的?？尚行约s束條件重量之和小于(cl+c2可剪去不滿(mǎn)足約束條件的子樹(shù)用cw記當(dāng)前的裝載重量，即cw=(w1x1+w2x2+...+wjxj),當(dāng)cw>c1時(shí)，以節(jié)點(diǎn)Z為根的子樹(shù)中所有節(jié)點(diǎn)都不滿(mǎn)足約束條件，因而該子樹(shù)中解均為不可行解，故可將該子樹(shù)剪去。3.2代碼#include<iostream>usingnamespacestd;template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]);intmain(){intn=3,m;intc=50,c2=50;intw[4]={0,10,40,40};intbestx[4];m二MaxLoading(w,c,n,bestx);cout<<”輪船的載重量分別為："<<endl;cout<<"c(1)="<<c<<",c(2)="<<c2<<endl;cout<<"待裝集裝箱重量分別為:"<<endl;cout<<"w(i)=”；for(inti=1;i<=n;i++){cout<<w[i]<<"";}cout<<endl;cout<<"回溯選擇結(jié)果為："<<endl;cout<<"m(1)="<<m<<endl;cout<<"x(i)=”；for(inti=1;i<=n;i++)cout<<bestx[i]<<””;}cout<<endl;intm2=0;for(intj=1;j<=n;j++){m2=m2+w[j]*(1-bestx[j]);}cout<<"m(2)="<<m2<<endl;if(m2>c2){cout<<"因?yàn)閙(2)大于c(2),所以原問(wèn)題無(wú)解！"<<endl;}return0;}template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[])/迭代回溯法,返回最優(yōu)載重量及其相應(yīng)解，初始化根結(jié)點(diǎn){inti=1;〃當(dāng)前層,x[1:i-1]為當(dāng)前路徑int*x=newint[n+1];Typebestw=0,//當(dāng)前最優(yōu)載重量cw=0,〃當(dāng)前載重量r=0;//剩余集裝箱重量for(intj=1;j<=n;j++){r+=w[j];}while(true)//搜索子樹(shù){while(i<=n&&cw+w[i]〈=c)//進(jìn)入左子樹(shù){r-=w[i];cw+=w[i];x[i]=1;i++;}if(i>n)〃到達(dá)葉結(jié)點(diǎn){for(intj=1j<=nj++){bestx[j]=x[j];}bestw二cw;}else//進(jìn)入右子樹(shù){r-=w[i];x[i]=0;i++;}while(cw+r〈=bestw){//剪枝回溯i--;while(i>0&&!x[i]){r+=w[i];i--;}//從右子樹(shù)返回if(i==0){delete[]x;returnbestw;}x[i]=0;cw-=w[i];i++；}}}3.3測(cè)試截圖輪船的載重量分別為：際裝集裝箱重量分別為;回溯選擇結(jié)果為：>c<i>=l1Sf(<2>=4S請(qǐng)按任意鍵繼續(xù).一4回朔法■遞歸4.1算法分析與回朔法-迭代的相同，以下代碼只是更改了具體的實(shí)現(xiàn)過(guò)程4.2代碼#include<iostream>usingnamespacestd;template<classType>classLoading{//friendTypeMaxLoading(Type[],Type,int,int[]);//private:public:voidBacktrack(inti);intn,//集裝箱數(shù)*x,//當(dāng)前解*bestx;〃當(dāng)前最優(yōu)解Type*w,//集裝箱重量數(shù)組c,//第一艘輪船的載重量cw,//當(dāng)前載重量bestw,//當(dāng)前最優(yōu)載重量r;〃剩余集裝箱重量};template<classType>voidLoading<Type>::Backtrack(inti);TypeMaxLoading(Typew[],Typec,intn,intbestx[]);intmain(){intn=3,m;intc=50,c2=50;intw[4]={0,10,40,40};intbestx[4];m二MaxLoading(w,c,n,bestx);cout<<"輪船的載重量分別為："<<endl;cout<<"c(1)="<<c<<",c(2)="<<c2<<endl;cout<<"待裝集裝箱重量分別為："<<endl;cout<<"w(i)=”；for(inti=1;i<=n;i++){cout<<w[i]<<"";}cout<<endl;cout<<"回溯選擇結(jié)果為："<<endl;cout<<"m(1)="<<m<<endl;cout<<"x(i)=”；for(inti=1;i<=n;i++){cout<<bestx[i]<<””;}cout<<endl;intm2=0;for(intj=1;j<=n;j++){m2=m2+w[j]*(1-bestx[j]);}cout<<"m(2)="<<m2<<endl;if(m2>c2){cout<<"因?yàn)閙(2)大于c(2),所以原問(wèn)題無(wú)解！"<<endl;return0;}template<classType>voidLoading<Type>::Backtrack(inti)//搜索第i層結(jié)點(diǎn){if(i>n)//到達(dá)葉結(jié)點(diǎn){if(cw>bestw){for(intj=1;j<=nj++){bestx[j]=x[j];//更新最優(yōu)解bestw二cw;}}return;}r-=w[i];if(cw+w[i]<=c)//搜索左子樹(shù)x[i]=1；cw+=w[i];Backtrack(i+1);cw-=w[i];}if(cw+r>bestw){x[i]=0;//搜索右子樹(shù)Backtrack(i+1);}r+=w[i];}template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[])//返回最優(yōu)載重量{Loading<Type>X;//初始化XX.x二newint[n+1];X.w=w;X.c=c;X.n=n;X.bestx二bestx;X.bestw=0;X.cw=0;//初始化rX.r=0;for(inti=1;i<=n;i++){X.r+=w[i];}X.Backtrack(1);delete[]X.x;returnX.bestw;}4.3測(cè)試截圖輪船的載直量分別為：g<±>-50,c<2>-50待