文档介绍：浙江工业大学计算机科学与技术学院
韩姗姗
ACM 程序设计竞赛入门 ——动态规划
主要内容
动态规划的引入
1
动态规划典型例题
2
例题引入(1)
例题引入—事件序列问题
假设每个事件的价值是不一样的。事件序列包含的事件的价值总和,称为该事件序列的总价值。请编程找出一个总价值最高的事件序列。
例题引入(2-1)
事件序列问题——题目分析
有没有有效的贪心算法?
假设事件序列按结束时间升序排列,如何找到一个最优解?
Value=2
Value=3
Value=3
Value=6
Value=4
Value=5
例题引入(2-2)
事件序列问题——题目分析
能不能分解成子问题?分治?
换种思路:假设有一个最优解Opt,那么有两种可能:
Opt包含了最后一个事件n
Opt没有包含最后一个事件n
也就是说,n个事件的最优解有两种可能性:
前 n-1个事件的最优解
第n个事件+ 前n-1个事件中不和第n个事件重叠的事件的最优解
例题引入(2-3)
事件序列问题——代码思路
Opt (n)
{ k=不和第n个事件重叠的个数;(已排序,第k+1个区间开始重叠)
If (n==0) 则返回空序列;
Else {
m1= Opt(n-1) 形成序列(s1)的价值;
m2= Vn+Opt(k) 形成序列(s2)的价值
if(m1<m2) 选择 s2+ Event n
else 选择 s1
return 序列;
}
例题引入(2-4)
事件序列问题——思路分析
Opt(6)
Opt(5)
Opt(3)
Opt(4)
Opt(3)
Opt(3)
Opt(1)
Opt(2)
Opt(1)
Opt(2)
Opt(1)
Opt(2)
Opt(1)
Opt(1)
Opt(1)
例题引入(2-5)
事件序列问题——思路分析
有很多重复计算,将耗费指数时间。
(还记得分治策略的适用原则吗?)
其实只需要计算Opt(1), Opt(2), Opt(3), …..Opt(n) n个子问题就可以了。
所以,可以在每个Opt第一次计算时把计算结果存储好,在后面需要时可以使用这些预先算好的值。(备忘录)
于是,可以写一个更聪明的算法:
例题引入(3-1)
事件序列问题——思路改进
Opt (n){
k=不和第n个事件重叠的个数;(已排序,第k+1个区间开始重叠)
If (n==0) 则返回空序列;
If (M[n]不空)则返回 M[n];
Else {
m1= Opt(n-1) 形成序列(s1)的价值;
m2= Vn+Opt(k) 形成序列(s2)的价值
if(m1<m2) M[n]= s2 +Event n
else 选择 M[n]= s1
return 序列M[n];
}