算法分析与设计实验报告-0-1背包问题、旅行售货员问题

实验报告课程计算机算法设计与分析实验名称0-1背包问题、旅行售货员问题学号姓名实验日期：实验五0-1背包问题、旅行售货员问题一．实验目的学习0-1背包问题的简单算法，掌握原理，运用C++编程实现。学习旅行售货员问题的简单算法，掌握原理，运用C++编程实现。二．实验内容（1）设计0-1背包问题的算法，上机编程实现。（2）设计旅行售货员问题的算法，上机编程实现。三．实验代码1.0-1背包问题的程序代码如下：#include<iostream>#include<stack>usingnamespacestd;#defineN100classHeapNode//定义HeapNode结点类{public:doubleupper,price,weight;//upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量intlevel,x[N];//活节点在子集树中所处的层序号};doubleMaxBound(inti);doubleKnap();voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlevel);stack<HeapNode>High;//最大队Highdoublew[N],p[N];//把物品重量和价值定义为双精度浮点数doublecw,cp,c=100;//cw为当前重量，cp为当前价值，定义背包容量为100intn=5;//货物数量为3intmain(){cout<<"请按顺序输入5个物品的重量：（按回车键区分每个物品的重量）"<<endl;inti;for(i=1;i<=n;i++)cin>>w[i];//输入5个物品的重量cout<<"请按顺序输入5个物品的价值：（按回车键区分每个物品的价值）"<<endl;for(i=1;i<=n;i++)cin>>p[i];//输入5个物品的价值cout<<"最大价值为：";cout<<Knap()<<endl;//调用knap函数输出最大价值return0;}doubleMaxBound(intj)//MaxBound函数求最大上界{doubleleft=c-cw,b=cp;//剩余容量和价值上界while(j<=n&&w[j]<=left)//以物品单位重量价值递减装填剩余容量{left-=w[j];b+=p[j];j++;}if(j<=n)b+=p[j]/w[j]*left;//装填剩余容量装满背包returnb;}voidAddLiveNode(doubleup,doublecp,doublecw,boolch,intlev)//将一个新的活结点插入到子集数和最大堆High中{HeapNodebe;be.upper=up;be.price=cp;be.weight=cw;be.level=lev;if(lev<=n)High.push(be);//调用stack头文件的push函数}doubleKnap()//优先队列分支限界法，返回最大价值，bestx返回最优解{inti=1;cw=cp=0;doublebestp=0,up=MaxBound(1);//调用MaxBound求出价值上界，best为最优值while(1)//非叶子结点{doublewt=cw+w[i];if(wt<=c)//左儿子结点为可行结点{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)//右子数可能含最优解AddLiveNode(up,cp,cw,false,i+1);if(High.empty())returnbestp;HeapNodenode=High.top();//取下一扩展结点High.pop();cw=node.weight;cp=node.price;up=node.upper;i=node.level;}}2.旅行售货员问题的程序代码如下：#include<stdio.h>#include<istream>usingnamespacestd;//---------------------宏定义------------------------------------------#defineMAX_CITY_NUMBER10//城市最大数目#defineMAX_COST10000000//两个城市之间费用的最大值//---------------------全局变量----------------------------------------intCity_Graph[MAX_CITY_NUMBER][MAX_CITY_NUMBER];//表示城市间边权重的数组intCity_Size;//表示实际输入的城市数目intBest_Cost;//最小费用intBest_Cost_Path[MAX_CITY_NUMBER];//最小费用时的路径//------------------------定义结点---------------------------------------typedefstructNode{intlcost;//优先级intcc;//当前费用intrcost;//剩余所有结点的最小出边费用的和ints;//当前结点的深度，也就是它在解数组中的索引位置intx[MAX_CITY_NUMBER];//当前结点对应的路径structNode*pNext;//指向下一个结点}Node;//---------------------定义堆和相关对操作--------------------------------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;//将传进来的结点信息copy一份保存//这样在函数外部对node的修改就不会影响到堆了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)){//发现一个优先级大的，则置于其前面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;}//---------------------分支限界法找最优解--------------------------------voidTraveler(){inti,j;inttemp_x[MAX_CITY_NUMBER];Node*pNode=NULL;intminiSum;//所有结点最小出边的费用和intminiOut[MAX_CITY_NUMBER];//保存每个结点的最小出边的索引MiniHeap*heap=newMiniHeap;//分配堆InitMiniHeap(heap);//初始化堆miniSum=0;for(i=0;i<City_Size;i++){miniOut[i]=MAX_COST;//初始化时每一个结点都不可达for(j=0;j<City_Size;j++){if(City_Graph[i][j]>0&&City_Graph[i][j]<miniOut[i]){//从i到j可达，且更小miniOut[i]=City_Graph[i][j];}}if(miniOut[i]==MAX_COST){//i城市没有出边Best_Cost=-1;return;}miniSum+=miniOut[i];}for(i=0;i<City_Size;i++){//初始化的最优路径就是把所有结点依次走一遍Best_Cost_Path[i]=i;}Best_Cost=MAX_COST;//初始化的最优费用是一个很大的数pNode=newNode;//初始化第一个结点并入堆pNode->lcost=0;//当前结点的优先权为0也就是最优pNode->cc=0;//当前费用为0（还没有开始旅行）pNode->rcost=miniSum;//剩余所有结点的最小出边费用和就是初始化的miniSumpNode->s=0;//层次为0pNode->pNext=NULL;for(intk=0;k<City_Size;k++){pNode->x[k]=Best_Cost_Path[k];//第一个结点所保存的路径也就是初始化的路径}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];//将最优路径置换为当前结点本身所保存的}/***pNode结点保存的路径中的含有这条路径上所有结点的索引**x路径中保存的这一层结点的编号就是x[City_Size-2]**下一层结点的编号就是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表示不可达//叶子可达起点费用更低Best_Cost=pNode->cc+edge1+edge2;pNode->cc=Best_Cost;pNode->lcost=Best_Cost;//优先权为Best_CostpNode->s++;//到达叶子层}}else{//内部结点for(i=pNode->s;i<City_Size;i++){//从当前层到叶子层if(City_Graph[pNode->x[pNode->s]][pNode->x[i]]>=0){//可达//pNode的层数就是它在最优路径中的位置inttemp_cc=pNode->cc+City_Graph[pNode->x[pNode->s]][pNode->x[i]];inttemp_rcost=pNode->rcost-miniOut[pNode->x[pNode->s]];//下一个结点的剩余最小出边费用和//等于当前结点的rcost减去当前这个结点的最小出边费用if(temp_cc+temp_rcost<Best_Cost){//下一个结点的最小出边费用和小于当前的最优解，说明可能存在更优解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];//将当前结点的编号放入路径的深度为s+1的地方temp_x[i]=Best_Cost_Path[pNode->s+1];//将原路//径中的深度为s+1的结点编号放入当前路径的//相当于将原路径中的的深度为i的结点与深度W为s+1的结点交换Node*pNextNode=newNo