算法分析与设计线下作业二样本.pdf

《算法分析与设计》

学习中心：
专业：
学号：
姓名：

作业练习二

一、名词解释

1、MST性质

2、子问题重叠性质

递归算法求解问题时，每次产生子问题并不总是新问题，有些子问题被重复计算多次，这种

性质称为子问题重叠性质。

二、简答题

1、简述动态规划算法求解基本要素。

答：动态规划算法求解基本要素涉及：

1)最优子构造是问题能用动态规划算法求解前提；

2)动态规划算法，对每一种子问题只解一次，而后将其解保存在一种表格中，当再次需要解

此子问题时，只是简朴地用常数时间查看一下成果，即重叠子问题。

2、备忘录办法和动态规划算法相比有何异同？简述之。

答：备忘录办法是动态规划算法变形。与动态规划算法同样，备忘录办法用表格保存已解决

子问题答案，在下次需要解此问题时，只要简朴地查看该子问题解答，而不必重新计算。备

忘录办法与动态规划算法不同是，备忘录办法递归方式是自顶向下，而动态规划算法则是自

底向上递归。因而，备忘录办法控制构造与直接递归办法控制构造相似，区别在于备忘录办
法为每个解过子问题建立了备忘录以备需要时查看，避免了相似子问题重复求解，而直接递

归办法没有此功能。

3、贪心算法求解问题重要具备哪些性质？简述之。

答：贪心算法求解问题普通具备二个重要性质：

一是贪心选取性质，这是贪心算法可行第一种基本要素；

另一种是最优子构造性质，问题最优子构造性质是该问题可用贪心算法求解核心特性。

三、算法编写及算法应用分析题

1、设计求解如下最大子段和问题动态规划算法。只需给出其递推计算公式即可。

最大子段和问题：给定由n个整数（也许为负整数）构成序列a1a2…an，求该序列形

如Σi≤k≤jak子段和最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，

所求最优值为max{0，max1≤i≤j≤nΣi≤k≤jak}。

2、关于多段图问题。设G＝(V，E)是一种赋权有向图，其顶点集V被划提成k>2个不相交

子集：1，其中，和分别只有一种顶点（称为源）和一种顶点（称为汇），
ViikV1Vkst

图中所有边（u,v），uV，vV。求由s到t最小成本途径。
ii1

①给出使用动态规划算法求解多段图问题基本思想。

②使用上述办法求解如下多段图问题。

V1V2V3V4V5
2
4
669
2
2
95
4
34
77
s17310212t
311
4
21151

8611
58

3、最优二元归并问题：已知将两个分别包括a个和b个记录已分类文献归并在一起得到一

种分类文献需作a+b次记录移动。既有n个已分类文献F1,F1,⋯,Fn，它们记录个数分别为l1，

l2,⋯，ln。当前考虑使用二元归并模式将这n个文献归并成一种分类文献，规定记录移动次

数至少。设计一种贪心算法来求解一种最优二元归并（即记录移动次数至少二元归并）。

4、带限期作业调度问题：n个作业需要在一台机器上解决，每个作业可在单位时间内完毕。

每个作业i均有一种截止期限di>0(di为整数)，当且仅当作业i在它截止期限之前被完毕，

获得pi>0效益。一种可行调度方案为n个作业一种子集J，其中J中每个作业都能在各自截

止期限内完毕。该可行调度方案效益是J中作业效益之和。试设计贪心算法求效益最大可行

调度方案（即最优调度方案）。