还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
四、实验结果后问题(回溯法)Z.D:\ZJC\Debug\N.ex—共共兴兴[solution1]——w QM MQ Q***Q*[solution21——兴兴**Q*Q*关共***Q wQPress anykey tocontinue实验五0・1背包问题(分支限界法)
一、实验目的与要求、掌握背包问题的算法;I0-
1、初步掌握分支限界法2
二、实验题问题描述利用分支限界法设计背包问题的算法0/1
三、实验代码#include stdio.h#includemalloc.h〃最多结点数#define MaxSize100typedef struct QNode|float weight;float value;int ceng;structQNode*parent;bool leftChild;}QNode,*qnode;〃存放每个结点typedef struct{qnode Q[MaxSize];int front,rear;存放结点的队歹!}SqQueue;//JSqQueue sq;〃最优解float bestv=0;intn=0;〃实际物品数物品的重量float w[MaxSize];//〃物品的价值float v[MaxSize];存放最优解int bestx[MaxSize];//qnode bestE;〃队列初始化void InitQueueSqQueuesq sq.front=l;sq.rear=l;〃队歹是否为空bool QueueEmptySqQueuesq Uifsq.front==sq.rearreturn true;elsereturn false;}〃入队void EnQueueSqQueuesq qnodeb9{ifsq.front==sq.rear+l%MaxSize{队列已满!”;printfC,sq.Q[sq.rear]=b;sq.rear=sq.rear+l%MaxSize;}〃出队qnode DeQueueSqQueuesq{qnode e;ifsq.front==sq.rear队列已空”;printfreturn0;}e=sq.Q[sq.front];sq.front=sq.front+l%MaxSize;return e;}void EnQueuelfloat wt,float vt,int i,QNode*parent,bool leftchildqnodeb;〃可行叶子结点if i==nif vt==bestvbestE=parent;bestx[n]=leftchildl:0;return;〃非叶子结点b=qnodemallocsizeofQNode;b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent;b-leftChild=leftchild;EnQueuesq,b;void maxLoadingfloatw[],float v[],int c{floatwt=0;float vt=0;〃当前的扩展结点所在的层int i=l;〃扩展结点所相应的当前载重量float ew=0;〃扩展结点所相应的价值float ev=0;qnode e=NULL;qnode t=NULL;InitQueuesq;EnQueuesq,t;〃空标志队列while IQueueEmptysqwt=ew+w[i];vt=ev+v[i];if wt=cifvtbestvbestv=vt;EnQueuel ew,ev,i,e,false;〃左儿子总是可行e=DeQueuesq;//取下一扩展结点if e==NULL//左儿子结点进队列EnQueuelwt,vt,i,e,true;if QueueEmptysqbreak;EnQueuesq,NULL;//同层结点尾部标志//取下一扩展结点e=DeQueuesq;i++;〃更新当前扩展结点的值ew=e-weight;ev=e-value;printf,最优取法为:\nH;〃构造最优解for int j=n-l;jO;j-bestx[j]=bestE-leftChildl:O;bestE=bestE-parent;forint k=l;k=n;k++ifbestx[k]==lprintfCXn物品%d重量%.lf,价值:%Jf\nH,k,w[k],v[k];printfu\nu;printf最优价值为%.lf\n\n H,bestv;int main{int c;printffloat ewv[MaxSize];printfC1rf lw请rlwejwej输wrjwrj-rlw入rlwrjwr.物wr.vrTwr品lw的数量\n;scanfn%du,n;printf「请输入背包的最大承重量\nu;scanfn%dn c;9printfn\n请输入物品的重量和单位重量价值\n\nH;forint i=l;i=n;i++{物品%出,”;printfscanfM%f%f\w[i],ewv[i];v[i]=w[i]*ewv[i];printfH\nH;maxLoadingw,v,c;return0;
四、实验结果F:\DC4-4-\Dev-Cpp\ConsolePauser.exe一背包分艮•^法共01PX-MXXMMMXX-XX*XXXXXMXXXXMX1CX请输入物品的数量信输入背包的最大承重量400请输入物品的重量和单位重量价值物品1:10056物品工25025物品3:30056物品4=5910最优取法为售韩章堇:产孙价值皿56般品E00r愀品2:15025卜勿品3:300E6「品459|10卜优取法为物品工重量价值
100.0,
5600.0物品重量价值
3300.0,
16800.0最优价值为
22400.0process exitedwith return ualue0[Press anykey tocontinue...檄软拼音半实验一棋盘覆盖递归与分治策略
一、实验目的与要求、明确棋盘覆盖的概念
1、明确递归与分治策略的设计思路
2、利用递归与分治策略解决棋盘覆盖问题3
二、实验题问题描述递归与分治策略算法,用种不同形态的型骨牌覆盖一个给定的特殊棋盘4L上除特殊方格以外的所有方格,且任何个型骨牌不得重叠覆盖输入数据由程2L序运行后的界面中的编辑框中输入游戏规模,特殊方格的位置将覆盖的结果在窗口中显示出来
三、实验代码#includeiostream.hint tile=l;int Board
[100]
[100];void ChessBoardint tr int tc,int dr,int de,int size9ifsize==lreturn;型骨牌号intt=tile++;//L〃分割棋盘int s=size/2;〃覆盖左上角子棋盘ifdrtr+sdctc+s〃特殊方格在此棋盘中ChessBoardtr,tc,dr,dc,s;else{//此棋盘中无特殊方格〃用号型骨牌覆盖右下角t LBoard[tr+s-1][tc+s-1]=t;〃覆盖其余方格ChessBoardtr,tc,tr+s-l,tc+s-l,s;〃覆盖右上角子棋盘ifdrtr+s dc=tc+s〃特殊方格在此棋盘中ChessBoardtr,tc+s,dr,dc,s;{〃此棋盘中无特殊方格else〃用号型骨牌覆盖左下角t LBoard[tr+s-1][tc+s]=t;〃覆盖其余方格ChessBoardtr,tc+s,tr+s-l,tc+s,s;〃覆盖左下角子棋盘ifdr=tr+s dctc+s〃特殊方格在此棋盘中ChessBoardtr+s,tc,dr,dc,s;{〃用号型骨牌覆盖右上角else tLBoard[tr+s][tc+s-1]=t;〃覆盖其余方格ChessBoardtr+s,tc,tr+s,tc+s-1,s;}〃覆盖右下角子棋盘ifdr=tr+s dc=tc+s〃特殊方格在此棋盘中ChessBoardtr+s,tc+s,dr,dc,s;{〃用号型骨牌覆盖左上角else tLBoard[tr+s][tc+s]=t;〃覆盖其余方格ChessBoardtr+s,tc+s,tr+s,tc+s,s;void main|int size;输入棋盘的大小必须是的次幕”;coutvv”size2ncin»size;int index_x,index_y;输入特殊方格位置的坐标”;coutvv”cin»index_x»index_y;ChessBoard0,0,index_x,mdex_y size;9forint i=0;isize;i++forint j=O;jsize;j++cout«Board[i][j]«n\tH;cout«endl;
四、实验结果输入棋盘的(大小必须是的次基)输入特殊方格位置的坐标size2n8333344889932248779526610107115560110111113131411181919131214141818171915121216201717211515161620202121Press anykey tocontinue实验二矩阵连乘问题动态规划
一、实验目的与要求、明确矩阵连乘的概念
1、利用动态规划解决矩阵连乘问题2
二、实验题问题描述给定个矩阵其中与知是可乘的,确定计算矩n{A1,A2,…,An},Ai Aii=l,2…,n-lo阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少输入数据为矩阵个数和每个矩阵规模,输出结果为计算矩阵连乘积的计算次序和最少数乘次数
三、实验代码#include Mstdafx.hn#include iostreamusing namespace std;const intL=7;〃递归求最优解int RecurMatrixChainint i,int j,int*p;〃构造最优解void Tracebackinti,int j,int**s;int mainintp[L]={30,35,35,5,10,20,25};int**s=new int*[L];forint i=0;iL;i++{s[i]=new int[L];}矩阵的最少计算次数为coutvv”vvRecurMatrixChain16s,Pvvendl;矩阵最优计算次序为coutv vvendl;Tracebackl,6,s;return0;}int RecurMatrixChaininti,intj,int**s,int*pifi==j return0;int u=RecurMatrixChaini,i,s,p+RecurMatrixChaini+lJ,s,p+p[i-l]i p[i]*p[j];s[i]U]=i;forint k=i+l;kj;k++intt=RecurMatrixChaini ks p+RecurMatrixChaink+1j,s,p+p[i-l]*p[k]*p[j];iftu999{u=t;s[i][j]=k;}returnu;}void Tracebackinti,intj,int**sifi==j return;Tracebacki,s[i]U],s;Tracebacks[i][j]+lj,s;cout«n Multiply An«i«n,n«s[i][j];cout«n and AH«s[i][j]+l«n,n«j«endl;}
四、实验结果矩阵的最少计算次数为15125矩阵最优计算次序为:Multiply A2,2and A3,3Multiply AlJ and A2,3Multiply A4,4and A5,5MultiplyA4,5andA6,6Multiply Al,3andA4,6Press anykey tocontinue实验三背包问题贪心算法
一、实验目的与要求、掌握背包问题的算法
1、初步掌握贪心算法2
二、实验题问题描述有一个背包容量为输入个物品,每个物品有重量以及物品放入背包中所得C,N W,的收益问选择放入的物品,不超过背包的容量,且得到的收益最好P
三、实验代码#includeiostreamusing namespacestd;物品结构体struct.Object//〃物品价值int Value;〃物品重量int Weight;〃物品单位价值int AveValue;物品可以放入的数量float Num;//;void knaspsackintn,float M,.Object object[]{〃n为物品个数,M为背包容量inti;float C=M;fori=0;in;i++{〃初始化放入背包的物品为objects.Num=0;0〃当物品重量大于背包容量时ifobject[i].WeightCbreak;〃小于时else|〃物品放入一件object[i].Num=l;iC・=object[i].Weight;〃背包容量减小}〃当不能放入整个物品时,选取物品一部分放入}ifiv=nobject[i].Num=C/object[i].Weight;fori=0;in;i++{ifobject[i].Num0coutvv”重量为H«object[i].Weight«n价值为n«object[i].Value«n的物品放入件vvobject[i].Numvv vvendl;〃将各个物品按单位价值进行排序void SortObject_Object object[],int nintj;_Object temp;inti;fori=0;in;i++objecttil.AveValue^bjectEil.Value/objectfil.Weight;//^^^/品的单位价值fori=0;ivn・〃根据物品的单位价值对物品进行从大到小的冒泡排序l;i++forj=0;jn-i-l;j++ifobject[j].AveValueobject[j+l].Ave Valuetemp=object[j];object[j]=object[j+l];object[j+l]=temp;}}个物品int main{_Object object
[4];//4〃背包容量为int M=9;15object
[0].Weight=2;object
[0].Value=3;object[l].Weight=3;object[l].Value=4;object
[2].Weight=4;object
[2].Value=5;object
[3].Weight=5;object
[3].Value=7;SortObjectobject,4;knaspsack4,M,object;}
四、实验结果重量为:价值为:的物品放入件231重量为:价值为:的物品放入件341重量为:价值为:的物品放入件451Press anykey tocontinue实验四后问题(回溯法)N
一、实验目的与要求、明确回溯算法的设计策略
1、利用回溯法解决后问题2N
二、实验题问题描述要求在一个格的棋盘上放置个皇后,使得他们彼此不攻击按照国际nXn n象棋的规则,一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子因此,后问题等价于要求在一个格的棋盘上放置个皇后,使得任n nXnn何个皇后不能被放在同一行或同一列或同一斜线上求出问题的所有解2
三、实验代码#include iostream#include vector#include cmathusingnamespacestd;struct Point{Pointint_x,int_y:x_x,y_y{}int x;inty;;class QueenProblem{public:QueenProblemint_n:n_n{}{}〜QueenProblembool checkvectorPoint vp,Point p;void solve;void print;private:intn;vectorvectorPointvvp;};bool QueenProbIem::checkvectorPointvp,Point pfor inti=0;ivp.sizeQ;++i{if vp[i].x==p.x||vp[i].y==p.y||absvp[i].y-p.y==absvp[i].x-p.x。