最大字段和实验报告

最大字段和1.实验目的和要求〔1〕深刻掌握动态规划法的设计思想并能熟练运用；〔2〕理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。〔3〕分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；〔4〕比拟不同算法的时间性能；〔5〕给出测试数据，写出程序文档2.实验内容给定由n个整数组成的序列(a1,a2,…,an)，求该序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。3.实验环境TurboC或VC++4.实验学时2学时，必做实验5.数据结构与算法数据结构:程序中所用的数据都是储存在数组当中算法:蛮力法函数MaxSum(inta[],intn,int&besti,int&bestj)分治法函数MaxSum(inta[],intleft,intright)动态规划法函数MaxSum(intn,inta[])6.核心源代码及时间性能分析〔1〕蛮力法：#include<iostream.h>intMaxSum(inta[],intn,int&besti,int&bestj){intsum=0;inti,j,k;for(i=1;i<=n;i++){intasum=0;for(j=i;j<=n;j++){asum+=a[j];if(asum>sum){sum=asum;besti=i;bestj=j;}}}returnsum;}voidmain(){intn,a[cout<<"请输入各元素的值(一共"<100],m,i,j,maxsum;cout<<"请输入整数序列的元素个数n:"<<endl;cin>>n;<n<<"个):"<<endl;for(m=1;m<=n;m++)cin>>a[m];maxsum=MaxSum(a,n,i,j);cout<<"整数序列的最大子段和是："<<maxsum<<endl;}时间性能：T(n)=O(n²)结果截图：〔2〕分治法：#include<iostream.h>intMaxSum(inta[],intleft,intright){intsum=0;if(left==right) {if(a[left]>0)sum=a[left];elsesum=0;}else{intcenter=(left+right)/2;intleftsum=MaxSum(a,left,center);intrightsum=MaxSum(a,center+1,right);ints1=0;intlefts=0;for(inti=center;i>=left;i--) {lefts+=a[i];if(lefts>s1) s1=lefts;}ints2=0;intrights=0;for(intj=center+1;j<=right;j++) {rights+=a[j];if(rights>s2) s2=rights;}sum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;}returnsum;}voidmain(){intn,a[100],m,maxsum;cout<<"请输入整数序列的元素个数n:"<<endl;cin>>n;cout<<"请输入各元素的值(一共"<<n<<"个):"<<endl;for(m=1;m<=n;m++)cin>>a[m];maxsum=MaxSum(a,1,n);cout<<"整数序列的最大子段和是："<<maxsum<<endl;}时间性能：T(n)=O(nlog2(n))结果截图：〔3〕动态规划法：#include<iostream.h>voidMaxSum(intn,inta[]){intsum=0;intb=0;for(inti=1;i<=n;i++){if(b>0) b+=a[i];else b=a[i];if(b>sum) sum=b;} cout<<"整数序列的最大子段和是："<<sum<<endl;}voidmain(){intn,a[100],m,maxsum;cout<<"请输入整数序列的元素个数n:"<<endl;cin>>n;cout<<"请输入各元素的值(一共"<<n<<"个):"<<endl;for(m=1;m<=n;m++)cin>>a[m];MaxSum(n,a);}时间性能：T(n)=O(n)结果截图：背包问题1.实验题目：分别用贪心法法和分支限界法求解背包问题2.实验内容：0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包屡次，也不能只装入局部的物品i。3.实验源程序：〔1〕贪心法：#include<iostream.h>structgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品该放的数量intflag;//物品编号};//物品信息结构体voidInsertionsort(goodinfogoods[],intn){intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].p>goods[i].p){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}//按物品效益，重量比值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=1;i<n;i++){if(goods[i].w>cu)//当该物品重量大与剩余容量跳出break;goods[i].X=1;cu=cu-goods[i].w;//确定背包新的剩余容量}if(i<=n)goods[i].X=cu/goods[i].w;//该物品所要放的量/*按物品编号做降序排列*/for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].flag<goods[i].flag){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}cout<<"最优解为:"<<endl;for(i=1;i<=n;i++){cout<<"第"<<i<<"件物品要放:";cout<<goods[i].X<<endl;}}voidmain(){cout<<"|--------运用贪心法解背包问题---------|"<<endl;cout<<"|---powerby李奇蓬---|"<<endl;cout<<"|-------------------------------------|"<<endl;intj;intn;floatM;goodinfo*goods;//定义一个指针while(j){cout<<"请输入物品的总数量：";cin>>n;goods=newstructgoodinfo[n+1];//cout<<"请输入背包的最大容量：";cin>>M;cout<<endl;inti;for(i=1;i<=n;i++){goods[i].flag=i;cout<<"请输入第"<<i<<"件物品的重量:";cin>>goods[i].w;cout<<"请输入第"<<i<<"件物品的效益:";cin>>goods[i].p;goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比cout<<endl;}Insertionsort(goods,n);bag(goods,M,n);cout<<"press<1>torunagian"<<endl;cout<<"press<0>toexit"<<endl;cin>>j;}}结果截图：〔2〕分支限界法：#include<stdio.h>#include<malloc.h>#defineMaxSize100//最多结点数typedefstructQNode{ floatweight;floatvalue;int ceng;structQNode*parent;boolleftChild;}QNode,*qnode;//存放每个结点typedefstruct{ qnodeQ[MaxSize];intfront,rear;}SqQueue;//存放结点的队列SqQueuesq;floatbestv=0;//最优解intn=0;//实际物品数floatw[MaxSize];//物品的重量floatv[MaxSize]; //物品的价值intbestx[MaxSize];//存放最优解qnodebestE;voidInitQueue(SqQueue&sq)//队列初始化{ sq.front=1; sq.rear=1;}boolQueueEmpty(SqQueuesq)//队列是否为空{ if(sq.front==sq.rear) returntrue; else returnfalse;}voidEnQueue(SqQueue&sq,qnodeb)//入队{ if(sq.front==(sq.rear+1)%MaxSize) { printf("队列已满!"); return; } sq.Q[sq.rear]=b; sq.rear=(sq.rear+1)%MaxSize;}qnodeDeQueue(SqQueue&sq)//出队{ qnodee; if(sq.front==sq.rear) { printf("队列已空!"); return0; } e=sq.Q[sq.front]; sq.front=(sq.front+1)%MaxSize; returne;}voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild){ qnodeb; if(i==n)//可行叶子结点 { if(vt==bestv) { bestE=parent; bestx[n]=(leftchild)?1:0; } return; } b=(qnode)malloc(sizeof(QNode));//非叶子结点 b->weight=wt; b->value=vt; b->ceng=i; b->parent=parent; b->leftChild=leftchild; EnQueue(sq,b);}voidmaxLoading(floatw[],floatv[],intc){ floatwt=0; floatvt=0; inti=1;//当前的扩展结点所在的层 floatew=0;//扩展节点所相应的当前载重量 floatev=0;//扩展结点所相应的价值 qnodee=NULL; qnodet=NULL; InitQueue(sq); EnQueue(sq,t);//空标志进队列 while(!QueueEmpty(sq)) { wt=ew+w[i]; vt=ev+v[i]; if(wt<=c) { if(vt>bestv) bestv=vt; EnQueue1(wt,vt,i,e,true);//左儿子结点进队列 } EnQueue1(ew,ev,i,e,false);//右儿子总是可行； e=DeQueue(sq);//取下一扩展结点 if(e==NULL) { if(QueueEmpty(sq))break; EnQueue(sq,NULL);//同层结点尾部标志 e=DeQueue(sq);//取下一扩展结点 i++; } ew=e->weight;