最大字段和實(shí)驗(yàn)報(bào)告

最大字段和1.實(shí)驗(yàn)?zāi)康暮鸵蟆?〕深刻掌握動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想并能熟練運(yùn)用；〔2〕理解這樣一個(gè)觀點(diǎn)：同樣的問題可以用不同的方法解決，一個(gè)好的算法是反復(fù)努力和重新修正的結(jié)果。〔3〕分別用蠻力法、分治法和動(dòng)態(tài)規(guī)劃法設(shè)計(jì)最大子段和問題的算法；〔4〕比擬不同算法的時(shí)間性能；〔5〕給出測試數(shù)據(jù)，寫出程序文檔2.實(shí)驗(yàn)內(nèi)容給定由n個(gè)整數(shù)組成的序列(a1,a2,…,an)，求該序列形如的子段和的最大值，當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)，其最大子段和為0。3.實(shí)驗(yàn)環(huán)境TurboC或VC++4.實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)，必做實(shí)驗(yàn)5.數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu):程序中所用的數(shù)據(jù)都是儲(chǔ)存在數(shù)組當(dāng)中算法:蠻力法函數(shù)MaxSum(inta[],intn,int&besti,int&bestj)分治法函數(shù)MaxSum(inta[],intleft,intright)動(dòng)態(tài)規(guī)劃法函數(shù)MaxSum(intn,inta[])6.核心源代碼及時(shí)間性能分析〔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<<"請輸入整數(shù)序列的元素個(gè)數(shù)n:"<<endl;cin>>n;<n<<"個(gè)):"<<endl;for(m=1;m<=n;m++)cin>>a[m];maxsum=MaxSum(a,n,i,j);cout<<"整數(shù)序列的最大子段和是："<<maxsum<<endl;}時(shí)間性能：T(n)=O(n2)結(jié)果截圖：〔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<<"請輸入整數(shù)序列的元素個(gè)數(shù)n:"<<endl;cin>>n;cout<<"請輸入各元素的值(一共"<<n<<"個(gè)):"<<endl;for(m=1;m<=n;m++)cin>>a[m];maxsum=MaxSum(a,1,n);cout<<"整數(shù)序列的最大子段和是："<<maxsum<<endl;}時(shí)間性能：T(n)=O(nlog2(n))結(jié)果截圖：〔3〕動(dòng)態(tài)規(guī)劃法：#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<<"整數(shù)序列的最大子段和是："<<sum<<endl;}voidmain(){intn,a[100],m,maxsum;cout<<"請輸入整數(shù)序列的元素個(gè)數(shù)n:"<<endl;cin>>n;cout<<"請輸入各元素的值(一共"<<n<<"個(gè)):"<<endl;for(m=1;m<=n;m++)cin>>a[m];MaxSum(n,a);}時(shí)間性能：T(n)=O(n)結(jié)果截圖：背包問題1.實(shí)驗(yàn)題目：分別用貪心法法和分支限界法求解背包問題2.實(shí)驗(yàn)內(nèi)容：0-1背包問題：給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?在選擇裝入背包的物品時(shí)，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包屢次，也不能只裝入局部的物品i。3.實(shí)驗(yàn)源程序：〔1〕貪心法：#include<iostream.h>structgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品該放的數(shù)量intflag;//物品編號(hào)};//物品信息結(jié)構(gòu)體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)//當(dāng)該物品重量大與剩余容量跳出break;goods[i].X=1;cu=cu-goods[i].w;//確定背包新的剩余容量}if(i<=n)goods[i].X=cu/goods[i].w;//該物品所要放的量/*按物品編號(hào)做降序排列*/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<<"最優(yōu)解為:"<<endl;for(i=1;i<=n;i++){cout<<"第"<<i<<"件物品要放:";cout<<goods[i].X<<endl;}}voidmain(){cout<<"|--------運(yùn)用貪心法解背包問題---------|"<<endl;cout<<"|---powerby李奇蓬---|"<<endl;cout<<"|-------------------------------------|"<<endl;intj;intn;floatM;goodinfo*goods;//定義一個(gè)指針while(j){cout<<"請輸入物品的總數(shù)量：";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;}}結(jié)果截圖：〔2〕分支限界法：#include<stdio.h>#include<malloc.h>#defineMaxSize100//最多結(jié)點(diǎn)數(shù)typedefstructQNode{ floatweight;floatvalue;int ceng;structQNode*parent;boolleftChild;}QNode,*qnode;//存放每個(gè)結(jié)點(diǎn)typedefstruct{ qnodeQ[MaxSize];intfront,rear;}SqQueue;//存放結(jié)點(diǎn)的隊(duì)列SqQueuesq;floatbestv=0;//最優(yōu)解intn=0;//實(shí)際物品數(shù)floatw[MaxSize];//物品的重量floatv[MaxSize]; //物品的價(jià)值intbestx[MaxSize];//存放最優(yōu)解qnodebestE;voidInitQueue(SqQueue&sq)//隊(duì)列初始化{ sq.front=1; sq.rear=1;}boolQueueEmpty(SqQueuesq)//隊(duì)列是否為空{(diào) if(sq.front==sq.rear) returntrue; else returnfalse;}voidEnQueue(SqQueue&sq,qnodeb)//入隊(duì){ if(sq.front==(sq.rear+1)%MaxSize) { printf("隊(duì)列已滿!"); return; } sq.Q[sq.rear]=b; sq.rear=(sq.rear+1)%MaxSize;}qnodeDeQueue(SqQueue&sq)//出隊(duì){ qnodee; if(sq.front==sq.rear) { printf("隊(duì)列已空!"); return0; } e=sq.Q[sq.front]; sq.front=(sq.front+1)%MaxSize; returne;}voidEnQueue1(floatwt,floatvt,inti,QNode*parent,boolleftchild){ qnodeb; if(i==n)//可行葉子結(jié)點(diǎn) { if(vt==bestv) { bestE=parent; bestx[n]=(leftchild)?1:0; } return; } b=(qnode)malloc(sizeof(QNode));//非葉子結(jié)點(diǎn) 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;//當(dāng)前的擴(kuò)展結(jié)點(diǎn)所在的層 floatew=0;//擴(kuò)展節(jié)點(diǎn)所相應(yīng)的當(dāng)前載重量 floatev=0;//擴(kuò)展結(jié)點(diǎn)所相應(yīng)的價(jià)值 qnodee=NULL; qnodet=NULL; InitQueue(sq); EnQueue(sq,t);//空標(biāo)志進(jìn)隊(duì)列 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);//左兒子結(jié)點(diǎn)進(jìn)隊(duì)列 } EnQueue1(ew,ev,i,e,false);//右兒子總是可行； e=DeQueue(sq);//取下一擴(kuò)展結(jié)點(diǎn) if(e==NULL) { if(QueueEmpty(sq))break; EnQueue(sq,NULL);//同層結(jié)點(diǎn)尾部標(biāo)志 e=DeQueue(sq);//取下一擴(kuò)展結(jié)點(diǎn) i++; } ew=e->weight;