动态规划算法时间效率的优化教程文件.pptx

《动态规划算法时间效率的优化教程文件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划算法时间效率的优化一、减少状态总数二、减少每个状态转移的状态数三、减少状态转移的时间1、改进状态表示；（例一）1、减少决策时间（例三）方法：采用恰当的数据结构；2、减少计算递推式的时间方法：进行预处理，利用计算结果等；2、其他方法：选取恰当的规划方向等；1、根据最优解的性质减少决策量；（例二）2、其他方法：利用四边形不等式证明决策的单调性等；例一、RaucousRockers演唱组（USACO`96）[问题描述]现有n首由RaucousRockers演唱组录制的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含

2、t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：(1)这组唱片中的歌曲必须按照它们创作的顺序排序；(2)包含歌曲的总数尽可能多。输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。设n首歌曲按照创作顺序排序后的长度为long[1..n]，则动态规划的状态表示描述为：g[i,j,k]，(0≤i≤n，0≤j≤m，0≤k

3、i]，i≥1时：g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}当k

4、钟。状态转移方程为：g[i,j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的计算方法为：当b+long[i]≤t时：a’=a;b’=b+long[i];当b+long[i]＞t时：a’=a+1;b’=long[i];规划的边界条件：当0≤i≤n时，g[i,0]=(0,0)题目所求的最大值是：answer=max{k

5、g[n,k]≤(m-1,t)}算法的时间复杂度为：O(n2)。Back例三、石子合并问题(NOI`95)[问题描述]在一个操场上摆放着一圈n堆石

6、子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。本例只考虑最大得分。i

7、，要么等于j-1，也就是说最优合并方案只可能是：{(i)(i+1…j)}或{(i…j-1)(j)}证明：设合并第i堆到第j堆石子的最优断开位置s[i,j]=p，且i

8、,p]+m[p+1,j]+t[i,j]+t[q+1,j]由于qt[p+1,j]与情况1是对称的。状态转移方程优化为：m[i,j]=max{m[i+1,j],m[i,j-1]}+t[i,j]i

9、只含26个小写英文字母a…z。单词表中的单词只有名词，动词和辅词这三种词性，且相同词性的单词互不相同。单词的个数不超过1000，单词的长度均不超过20。语法规则可简述为：名词短语：任意个辅词前缀接上一个名词；动词短语：任意个辅词前缀接上一个动词；句子：以名词短语开头，名词短语