文档介绍：该【动态规划算法作业 】是由【青山代下】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【动态规划算法作业 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..算法复杂性为0(n2)。算法分析3-4考虑下面的整数线性规划问题设计一个解此问题的动态规划算法,并分析算法的计算复杂性分析;这题是01背包问题的变种,只不过同一种物品可以重复屡次放入背包〔无件数限制〕,即所谓完全背包问题。wi对应第i件物品重量,vi对应第i件物品价值。从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。状态转移方程:f[v]=max{f[v-k*c]+k*w},其中0<=k*c<=v。完全背包问题有一个很简单有效的优化:假设两件物品i、j满足c<=c[j]且w>=w[j],那么将物品j去掉,不用考虑。由于有O(N*V)个状态需要求解,求解每个状态的时间那么不是常数了,求解状态f[v]的时间是O(v/c),,但是由于每件物品都可能取多件,总的复杂度就超过O(VN)了。算法分析3-7给定一个m×n的矩形网络,设其左上角为起点S。一辆汽车从起点S出发驶向右下角终点T。网格边上的数字表示距离。在假设干个网格点处设置了障碍,表示该网格点不可到达。试设计一个算法,求出汽车从起点S出发到达终点T的一条行驶路程最短的路线。分析:用一个集合R放置最短路径的所有网格点共m*n个。点集合中的点有其对应坐标原点〔0,0〕的横纵坐标x,y属性。用一个集合T记录所有边,边集合中的边有其边长和所连接的两点,对于mXn的矩行网络,有横向边(m+1)*n条,纵向边m*(n+1)条,。将所有边放入T集合,然后遍历去掉所有直接链接不可达点的边。剩下的就是一张可达的网格图,对于起点S和终点T,从S开始,可以采用图论的Dijkstra算法更新S到每个点的距离d。〔用距离记录集合M记录S到每个点的距离。〕d〔u〕=min(d(u),d(v)+w(v->u)).(u与v相邻)k+1k+1k+1也可以直接将不可达点的连接边长设置为无穷大,然后代入Dijkstra算法。算法实现题3-5编辑距离问题问题描述:设A和B是两个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:〔1〕删除一个字符;:..〔2〕插入一个字符;〔3〕将一个字符改为另一个字符将字符串A变换为字符串B所用的最少字符操作数成为字符串A到B的编辑距离,记为d(A,B).试设计一个有效算法,对任给的2个字符串A和B,计算他们的编辑距离d(A,B).算法设计:对给定的字符串A和B,计算其编辑距离d(A,B).。结果输出:将编辑距离d(A,B)#include<iostream>#include<>usingnamespacestd;//Globalvariablesint**tab;intm=0;intn=0;//functiondeclarevoidinit();voidfree();intd(char*str1,char*str2);intmain(){和距离为/*A和B距离*//**/FILE*fp;FILE*fp2;charAF[100];charBF[100];constchar*BP=BF;return0;return0;和距离为和%s距离为memcpy(AF,BP,strlen(BF));}:..if(fclose(fp)!=0)return0;/**/if(fclose(fp2)!=0)return0;/**/return0;}voidinit(){//cin>>m;//cin>>n;//malloctab=newint*[m];for(inti=0;i<m;i++)tab[i]=newint[n];//initfor(inti=0;i<m;i++){for(intj=0;j<n;j++){tab[i][j]=0;}}for(inti=0;i<m;i++)tab[i][0]=i;for(intj=0;j<n;j++)tab[0][j]=j;//returntrue;}voidfree(){for(inti=0;i<m;i++)deletetab[i];delete[]tab;}intd(char*str1,char*str2){m=strlen(str1);n=strlen(str2);//cout<<m<<endl;//cout<<n<<endl;if(m==0||n==0){:..returnm>n?m:n;}init();intcost=0;for(inti=1;i<m;i++){for(intj=1;j<n;j++){//计算替换操作的代价,如果两个字符相同,那么替换代价为0,否那么为1if(str1[i]==str2[j])cost=0;elsecost=1;if(tab[i-1][j]<tab[i][j-1]&&tab[i-1][j]+1<tab[i-1][j-1]+cost)tab[i][j]=tab[i-1][j]+1;elseif(tab[i][j-1]+1<tab[i-1][j-1]+cost){tab[i][j]=tab[i][j-1]+1;}else{tab[i][j]=tab[i-1][j-1]+cost;}}}intresult=tab[m-1][n-1];free();returnresult;}运行举例input01背包问题程序为ppt算法的实现:..1根本算法/***authorwd*title01背包〔algorithmisfromcourseppt〕*time2021-5-115:41:09*/#include<iostream>usingnamespacestd;//globalenvirenmentvariablesint*w;int*v;intnum=0;bool*x;typedefstructPoint{intx;inty;}point;//functionintm(inti,intj)//x[i]is0or1{if(i>num-1)return0;if(j>=w[i]){if(i==num-1){returnv[i];}else{intm1=m(i+1,j);intm2=m(i+1,j-w[i])+v[i];if(m1>m2){returnm1;}else{returnm2;}}}elseif(j>0&&j<w[i]){returnm(i+1,j);}elseif(j==0)return0;else{:..return0;}}voidinit(){for(inti=0;i<num;i++){cin>>w[i];x[i]=0;}fflush(stdin);for(inti=0;i<num;i++){cin>>v[i];}}intmain(){pointa;while(1){intcapacity,max_value=0;coutthenumberofitem(num)andcapacityofcin>>num;cin>>capacity;w=(int*)malloc(sizeof(int)*(num+1));v=(int*)malloc(sizeof(int)*(num+1));x=(bool*)malloc(sizeof(bool)*(num+1));//signiftheobjectisselectedinit();inti=0;max_value=m(i,capacity);free(w);free(v);free(x);}return0;}运行截图:..2改良算法#include<iostream>#include<vector>usingnamespacestd;//globalvarialesint*w;int*v;bool*x;intnum=0;intcapacity=0;intmax_value=0;typedefstructPoint{intx;inty;}point;typedefvector<point>vp;voidinit();voidshow_vp(vpp);bine_(vp&p,pointkey,vp&q);voidunion_(vp&p,vp&q,vp&r);voidshow_result(vpr);voidfree_();intmain(){vector<point>p;vector<point>q;vector<point>r;inti;pointstartp;=0;=0;pointpi;/*while(i>0){*/(startp);/*i--;}*/init();for(i=num-1;i>=0;i--){=w[i];=v[i];:..combine_(p,pi,q);//makequnion_(p,q,r);//makenextpp=r;//可以拷贝赋值}show_result(r);free_();//sothelastpoint'syvalueiswhatwewantnamelythebestvaluereturn0;}voidinit(){endl;cin>>num;cin>>capacity;w=(int*)malloc(sizeof(int)*(num+1));v=(int*)malloc(sizeof(int)*(num+1));x=(bool*)malloc(sizeof(bool)*(num+1));//signiftheobjectisselectedfor(inti=0;i<num;i++){cin>>w[i];x[i]=0;}fflush(stdin);for(inti=0;i<num;i++){cin>>v[i];}}bine_(vp&p,pointkey,vp&q){();for(vp::iteratori=();i<();i++){//cout<<(*i).x<<endl;pointtemp;=(*i).x+;=(*i).y+;if(>capacity);else:..(temp);}show_vp(q);}voidunion_(vp&p,vp&q,vp&r){();vp::iteratori=();vp::iteratorj=();while(i<()||j<())//双循环并行{pointtemp;if(i>=()){while(j<()){=(*j).x;=(*j).y;(temp);j++;}}elseif(j>=()){while(i<()){=(*i).x;=(*i).y;(temp);i++;}}else{if((*i).x<(*j).x){=(*i).x;=(*i).y;(temp);i++;}elseif((*i).x==(*j).x){if((*i).y==(*j).y){=(*i).x;=(*i).y;(temp);}else//x相等的统统跳过,记录一个就行{if((*i).y>(*j).y){:..=(*i).x;=(*i).y;(temp);}else{=(*j).x;=(*j).y;(temp);}}i++;j++;}else{=(*j).x;=(*j).y;(temp);j++;}}}//removeall(a,b)thata>=cbutb<dfromresulti=();show_vp(r);while((i+1)!=()){if((*i).y>(*(i+1)).y)(i+1);elsei++;}}voidshow_vp(vpp){intc=0;for(vp::iteratori=();i<();i++){}cout<<endl;}voidshow_result(vpr){vp::iteratori;i=()-1;:..}voidfree_(){free(w);free(v);free(x);}