算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告-0-1背包問(wèn)題、旅行售貨員問(wèn)題

實(shí)驗(yàn)報(bào)告課程計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)名稱0-1背包問(wèn)題、旅行售貨員問(wèn)題學(xué)號(hào)姓名實(shí)驗(yàn)日期：實(shí)驗(yàn)五0-1背包問(wèn)題、旅行售貨員問(wèn)題一．實(shí)驗(yàn)?zāi)康膶W(xué)習(xí)0-1背包問(wèn)題的簡(jiǎn)單算法，掌握原理，運(yùn)用C++編程實(shí)現(xiàn)。學(xué)習(xí)旅行售貨員問(wèn)題的簡(jiǎn)單算法，掌握原理，運(yùn)用C++編程實(shí)現(xiàn)。二．實(shí)驗(yàn)內(nèi)容（1）設(shè)計(jì)0-1背包問(wèn)題的算法，上機(jī)編程實(shí)現(xiàn)。（2）設(shè)計(jì)旅行售貨員問(wèn)題的算法，上機(jī)編程實(shí)現(xiàn)。三．實(shí)驗(yàn)代碼1.0-1背包問(wèn)題的程序代碼如下：#include<iostream>#include<stack>usingnamespacestd;#defineN100classHeapNode//定義HeapNode結(jié)點(diǎn)類{public:doubleupper,price,weight;//upper為結(jié)點(diǎn)的價(jià)值上界，price是結(jié)點(diǎn)所對(duì)應(yīng)的價(jià)值，weight為結(jié)點(diǎn)所相應(yīng)的重量intlevel,x[N];//活節(jié)點(diǎn)在子集樹(shù)中所處的層序號(hào)};doubleMaxBound(inti);doubleKnap();voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);stack<HeapNode>High;//最大隊(duì)Highdoublew[N],p[N];//把物品重量和價(jià)值定義為雙精度浮點(diǎn)數(shù)doublecw,cp,c=100;//cw為當(dāng)前重量，cp為當(dāng)前價(jià)值，定義背包容量為100intn=5;//貨物數(shù)量為3intmain(){cout<<"請(qǐng)按順序輸入5個(gè)物品的重量：（按回車鍵區(qū)分每個(gè)物品的重量）"<<endl;inti;for(i=1;i<=n;i++)cin>>w[i];//輸入5個(gè)物品的重量cout<<"請(qǐng)按順序輸入5個(gè)物品的價(jià)值：（按回車鍵區(qū)分每個(gè)物品的價(jià)值）"<<endl;for(i=1;i<=n;i++)cin>>p[i];//輸入5個(gè)物品的價(jià)值cout<<"最大價(jià)值為：";cout<<Knap()<<endl;//調(diào)用knap函數(shù)輸出最大價(jià)值return0;}doubleMaxBound(intj)//MaxBound函數(shù)求最大上界{doubleleft=c-cw,b=cp;//剩余容量和價(jià)值上界while(j<=n&&w[j]<=left)//以物品單位重量?jī)r(jià)值遞減裝填剩余容量{left-=w[j];b+=p[j];j++;}if(j<=n)b+=p[j]/w[j]*left;//裝填剩余容量裝滿背包returnb;}voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlev)//將一個(gè)新的活結(jié)點(diǎn)插入到子集數(shù)和最大堆High中{HeapNodebe;be.upper=up;be.price=cp;be.weight=cw;be.level=lev;if(lev<=n)High.push(be);//調(diào)用stack頭文件的push函數(shù)}doubleKnap()//優(yōu)先隊(duì)列分支限界法，返回最大價(jià)值，bestx返回最優(yōu)解{inti=1;cw=cp=0;doublebestp=0,up=MaxBound(1);//調(diào)用MaxBound求出價(jià)值上界，best為最優(yōu)值while(1)//非葉子結(jié)點(diǎn){doublewt=cw+w[i];if(wt<=c)//左兒子結(jié)點(diǎn)為可行結(jié)點(diǎn){if(cp+p[i]>bestp)bestp=cp+p[i];AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);}up=MaxBound(i+1);if(up>=bestp)//右子數(shù)可能含最優(yōu)解AddLiveNode(up,cp,cw,false,i+1);if(High.empty())returnbestp;HeapNodenode=High.top();//取下一擴(kuò)展結(jié)點(diǎn)High.pop();cw=node.weight;cp=node.price;up=node.upper;i=node.level;}}2.旅行售貨員問(wèn)題的程序代碼如下：#include<stdio.h>#include<istream>usingnamespacestd;//---------------------宏定義------------------------------------------#defineMAX_CITY_NUMBER10//城市最大數(shù)目#defineMAX_COST10000000//兩個(gè)城市之間費(fèi)用的最大值//---------------------全局變量----------------------------------------intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//表示城市間邊權(quán)重的數(shù)組intCity_Size;//表示實(shí)際輸入的城市數(shù)目intBest_Cost;//最小費(fèi)用intBest_Cost_Path[MAX_CITY_NUMBER];//最小費(fèi)用時(shí)的路徑//------------------------定義結(jié)點(diǎn)---------------------------------------typedefstructNode{intlcost;//優(yōu)先級(jí)intcc;//當(dāng)前費(fèi)用intrcost;//剩余所有結(jié)點(diǎn)的最小出邊費(fèi)用的和ints;//當(dāng)前結(jié)點(diǎn)的深度，也就是它在解數(shù)組中的索引位置intx[MAX_CITY_NUMBER];//當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的路徑structNode*pNext;//指向下一個(gè)結(jié)點(diǎn)}Node;//---------------------定義堆和相關(guān)對(duì)操作--------------------------------typedefstructMiniHeap{Node*pHead;//堆的頭}MiniHeap;//初始化voidInitMiniHeap(MiniHeap*pMiniHeap){pMiniHeap->pHead=newNode;pMiniHeap->pHead->pNext=NULL;}//入堆voidput(MiniHeap*pMiniHeap,Nodenode){Node*next;Node*pre;Node*pinnode=newNode;//將傳進(jìn)來(lái)的結(jié)點(diǎn)信息copy一份保存//這樣在函數(shù)外部對(duì)node的修改就不會(huì)影響到堆了pinnode->cc=node.cc;pinnode->lcost=node.lcost;pinnode->pNext=node.pNext;pinnode->rcost=node.rcost;pinnode->s=node.s;pinnode->pNext=NULL;for(intk=0;k<City_Size;k++){pinnode->x[k]=node.x[k];}pre=pMiniHeap->pHead;next=pMiniHeap->pHead->pNext;if(next==NULL){pMiniHeap->pHead->pNext=pinnode;}else{while(next!=NULL){if((next->lcost)>(pinnode->lcost)){//發(fā)現(xiàn)一個(gè)優(yōu)先級(jí)大的，則置于其前面pinnode->pNext=pre->pNext;pre->pNext=pinnode;break;//跳出}pre=next;next=next->pNext;}pre->pNext=pinnode;//放在末尾}}//出堆Node*RemoveMiniHeap(MiniHeap*pMiniHeap){Node*pnode=NULL;if(pMiniHeap->pHead->pNext!=NULL){pnode=pMiniHeap->pHead->pNext;pMiniHeap->pHead->pNext=pMiniHeap->pHead->pNext->pNext;}returnpnode;}//---------------------分支限界法找最優(yōu)解--------------------------------voidTraveler(){inti,j;inttemp_x[MAX_CITY_NUMBER];Node*pNode=NULL;intminiSum;//所有結(jié)點(diǎn)最小出邊的費(fèi)用和intminiOut[MAX_CITY_NUMBER];//保存每個(gè)結(jié)點(diǎn)的最小出邊的索引MiniHeap*heap=newMiniHeap;//分配堆InitMiniHeap(heap);//初始化堆miniSum=0;for(i=0;i<City_Size;i++){miniOut[i]=MAX_COST;//初始化時(shí)每一個(gè)結(jié)點(diǎn)都不可達(dá)for(j=0;j<City_Size;j++){if(City_Graph[i][j]>0&&City_Graph[i][j]<miniOut[i]){//從i到j(luò)可達(dá)，且更小miniOut[i]=City_Graph[i][j];}}if(miniOut[i]==MAX_COST){//i城市沒(méi)有出邊Best_Cost=-1;return;}miniSum+=miniOut[i];}for(i=0;i<City_Size;i++){//初始化的最優(yōu)路徑就是把所有結(jié)點(diǎn)依次走一遍Best_Cost_Path[i]=i;}Best_Cost=MAX_COST;//初始化的最優(yōu)費(fèi)用是一個(gè)很大的數(shù)pNode=newNode;//初始化第一個(gè)結(jié)點(diǎn)并入堆pNode->lcost=0;//當(dāng)前結(jié)點(diǎn)的優(yōu)先權(quán)為0也就是最優(yōu)pNode->cc=0;//當(dāng)前費(fèi)用為0（還沒(méi)有開(kāi)始旅行）pNode->rcost=miniSum;//剩余所有結(jié)點(diǎn)的最小出邊費(fèi)用和就是初始化的miniSumpNode->s=0;//層次為0pNode->pNext=NULL;for(intk=0;k<City_Size;k++){pNode->x[k]=Best_Cost_Path[k];//第一個(gè)結(jié)點(diǎn)所保存的路徑也就是初始化的路徑}put(heap,*pNode);//入堆while(pNode!=NULL&&(pNode->s)<City_Size-1){//堆不空不是葉子for(intk=0;k<City_Size;k++){Best_Cost_Path[k]=pNode->x[k];//將最優(yōu)路徑置換為當(dāng)前結(jié)點(diǎn)本身所保存的}/***pNode結(jié)點(diǎn)保存的路徑中的含有這條路徑上所有結(jié)點(diǎn)的索引**x路徑中保存的這一層結(jié)點(diǎn)的編號(hào)就是x[City_Size-2]**下一層結(jié)點(diǎn)的編號(hào)就是x[City_Size-1]*/if((pNode->s)==City_Size-2){//是葉子的父親intedge1=City_Graph[(pNode->x)[City_Size-2]][(pNode->x)[City_Size-1]];intedge2=City_Graph[(pNode->x)[City_Size-1]][(pNode->x)[0]];if(edge1>=0&&edge2>=0&&(pNode->cc+edge1+edge2)<Best_Cost){//edge1-1表示不可達(dá)//葉子可達(dá)起點(diǎn)費(fèi)用更低Best_Cost=pNode->cc+edge1+edge2;pNode->cc=Best_Cost;pNode->lcost=Best_Cost;//優(yōu)先權(quán)為Best_CostpNode->s++;//到達(dá)葉子層}}else{//內(nèi)部結(jié)點(diǎn)for(i=pNode->s;i<City_Size;i++){//從當(dāng)前層到葉子層if(City_Graph[pNode->x[pNode->s]][pNode->x[i]]>=0){//可達(dá)//pNode的層數(shù)就是它在最優(yōu)路徑中的位置inttemp_cc=pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];inttemp_rcost=pNode->rcost-miniOut[pNode->x[pNode->s]];//下一個(gè)結(jié)點(diǎn)的剩余最小出邊費(fèi)用和//等于當(dāng)前結(jié)點(diǎn)的rcost減去當(dāng)前這個(gè)結(jié)點(diǎn)的最小出邊費(fèi)用if(temp_cc+temp_rcost<Best_Cost){//下一個(gè)結(jié)點(diǎn)的最小出邊費(fèi)用和小于當(dāng)前的最優(yōu)解，說(shuō)明可能存在更優(yōu)解for(j=0;j<City_Size;j++){//完全copy路徑，以便下面修改temp_x[j]=Best_Cost_Path[j];}temp_x[pNode->x[pNode->s+1]]=Best_Cost_Path[i];//將當(dāng)前結(jié)點(diǎn)的編號(hào)放入路徑的深度為s+1的地方temp_x[i]=Best_Cost_Path[pNode->s+1];//將原路//徑中的深度為s+1的結(jié)點(diǎn)編號(hào)放入當(dāng)前路徑的//相當(dāng)于將原路徑中的的深度為i的結(jié)點(diǎn)與深度W為s+1的結(jié)點(diǎn)交換Node*pNextNode=newNo