算法分析与设计（线下作业二）

算法分析与设计（线下作业⼆）
《算法分析与设计》
学习中⼼：
专业：
学号：
姓名：
作业练习⼆
⼀、名词解释
1、MST性质
2、⼦问题的重叠性质
递归算法求解问题时，每次产⽣的⼦问题并不总是新问题，有些⼦问题被反复计算多次，这种性质称为⼦问题的重叠性质。

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

答：动态规划算法求解的基本要素包括：
1)最优⼦结构是问题能⽤动态规划算法求解的前提；
2)动态规划算法，对每⼀个⼦问题只解⼀次，⽽后将其解保存在⼀个表格中，当再次需要解此⼦问题时，只是简单地⽤常数时间查看⼀下结果，即重叠⼦问题。

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

答：备忘录⽅法是动态规划算法的变形。

与动态规划算法⼀样，备忘录⽅法⽤表格保存已解决的⼦问题的答案，在下次需要解此问题时，只要简单地查看该⼦问题的解答，⽽不必重新计算。

备忘录⽅法与动态规划算法不同的是，备忘录⽅法的递归⽅式是⾃顶向下的，⽽动态规划算法则是⾃底向上递归的。

因此，备忘录⽅法的控制结构与直接递归⽅法的控制结构相同，区别在于备忘录⽅法为每个解过的⼦问题建⽴了备忘录以备需要时查看，避免了相同的⼦问题的重复求解，⽽直接递归⽅法没有此功能。

3、贪⼼算法求解的问题主要具有哪些性质简述之。

答：贪⼼算法求解的问题⼀般具有⼆个重要的性质：
⼀是贪⼼选择性质，这是贪⼼算法可⾏的第⼀个基本要素；
另⼀个是最优⼦结构性质，问题的最优⼦结构性质是该问题可⽤贪⼼算法求解的关键特征。

三、算法编写及算法应⽤分析题
1、设计求解如下最⼤⼦段和问题的动态规划算法。

只需给出其递推计算公式即可。

最⼤⼦段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的⼦段和的最⼤值。

当所有整数均为负整数时定义其最⼤⼦段和为0。

依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。

2、关于多段图问题。

设G ＝(V ，E)是⼀个赋权有向图，其顶点集V 被划分成k>2个不相交的⼦集V i ：1i k ≤≤，其中，V 1和V k 分别只有⼀个顶点s （称为源）和⼀个顶点t （称为汇），图中所有的边（u,v ），i u V ∈，1i v V +∈。

求由s 到t 的最⼩成本路径。

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

②使⽤上述⽅法求解如下多段图问题。

s t
V1V2V3V4V5
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 中作业的效益之和。

试设计贪⼼算法求效益最⼤的可⾏调度⽅案（即最优调度⽅案）。