动态规划算法作业.pdfVIP

算法复杂性为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).

input.txtAB。

结果输出：将编辑距离d(A,B)输出到output.txt的第1行

程序代码

#includeiostream

#includestring.h

usingnamespacestd;

//Globalvariables

int**tab;

intm=0;

intn=0;

//functiondeclare

voidinit();

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)