动态规划算法作业

《动态规划算法作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划作业（所有算法实现代码承诺为本人自己编写并且截图为实际有效截图）作者：吴迪参考资料：课件ppt,百度百科算法分析3-1设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。分析：考虑一个拥有n个元素的数列{an}，欲找出其最长单调递增子序列，对于前i-1个元素组成的单调递增序列，考虑第ai个元素，最长单调递增子序列是否应该包含这个元素？如果它在序列中不是单增的，并且能确定前面的元素都是必定选中的，那么肯定它不被选入单增序列；如果它是单增的，仍然需要考虑它后面可能出现多于一个元素的单增子序列都比它要小的情况。所以在这样的条件

2、下，使用动态规划的方法，递归分析是合理的选择。用数列{bi}来记录数列{an}的最长单调递增子序列，0<=imax)max=b[i];}算法复杂性为0(n2)。算法

3、分析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)

4、个状态需要求解，求解每个状态的时间则不是常数了，求解状态f[v]的时间是O(v/c)，，但是由于每件物品都可能取多件，总的复杂度就超过O(VN)了。算法分析3-7给定一个m×n的矩形网络，设其左上角为起点S。一辆汽车从起点S出发驶向右下角终点T。网格边上的数字表示距离。在若干个网格点处设置了障碍，表示该网格点不可到达。试设计一个算法，求出汽车从起点S出发到达终点T的一条行驶路程最短的路线。分析：用一个集合R放置最短路径的所有网格点共m*n个。点集合中的点有其对应坐标原点（0,0）的横纵坐标x,y属性。用一个集合T记录所有边，边集合中的边有其边长和所连

5、接的两点，对于mXn的矩行网络，有横向边(m+1)*n条，纵向边m*(n+1)条，。将所有边放入T集合，然后遍历去掉所有直接链接不可达点的边。剩下的就是一张可达的网格图，对于起点S和终点T，从S开始，可以采用图论的Dijkstra算法更新S到每个点的距离d。（用距离记录集合M记录S到每个点的距离。）d（u）=min(d(u),d(vk+1)+w(vk+1->u)).(u与vk+1相邻)也可以直接将不可达点的连接边长设置为无穷大，然后代入Dijkstra算法。算法实现题3-5编辑距离问题问题描述：设A和B是两个字符串。要用最少的字符操作将字符串A转换为

6、字符串B。这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符改为另一个字符将字符串A变换为字符串B所用的最少字符操作数成为字符串A到B的编辑距离，记为d(A,B).试设计一个有效算法，对任给的2个字符串A和B，计算他们的编辑距离d(A,B).算法设计：对给定的字符串A和B，计算其编辑距离d(A,B).数据输入：由文件input.txt提供输入数据。文件的第一行是字符串A，文件的第二行是字符串B。结果输出：将编辑距离d(A,B)输出到output.txt的第1行程序代码#include#include<

7、string.h>usingnamespacestd;//Globalvariablesint**tab;intm=0;intn=0;//functiondeclarevoidinit();voidfree();intd(char*str1,char*str2);intmain(){char*A="sef";char*B="asesfe";//cout<

8、*fp2;charAF[100];charBF[100];constchar*BP=BF;if((fp=fo