动态规划的优化.ppt

动态规划的优化方法动态规划优化的内涵优化方法1：改进状态的表示方法一方法二方法三
[问题描述]
现有n首由RaucousRockers演唱组录制的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：
(1)这组唱片中的歌曲必须按照它们创作的顺序排序；
(2)包含歌曲的总数尽可能多。
输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。设n首歌曲按照创作顺序排序后的长度为long[1..n]，则动态规划的状态表示描述为：
g[i,j,k]，(0≤i≤n，0≤j≤m，0≤k<t),表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目。
状态转移方程为：
当k≥long[i]，i≥1时：
g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}
当k<long[i]，i≥1时：
g[i,j,k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}
规划的边界条件为：
当0≤j≤m，0≤k<t时：g[0,j,k]=0;
问题的最优解为：g[n,m,0]。改进的状态表示描述为：
g[i,j]=(a,b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲中选取j首录制所需的最少唱片为：a张唱片另加b分钟。
状态转移方程为：
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|g[n,k]≤(m-1,t)}优化方法2：利用决策的单调性分析最大子序和一个简化的问题
算法一——枚举简化方程用一个二叉堆来维护S(i-k)，每次求F(i)之前的操作如下：队列优化队列优化算法三算法三方法3：根据最优解的性质减少决策猜想证明：方法4:利用贪心思想减少状态总数分析优化贪心优化例7：Hotel先考虑夫妇这个限制考虑动态规划考虑优化方法4：利用恰当的数据结构存储状态，减少状态查找时间我们分别用v,u,a表示动词，名词和辅词，给出的文章用L[1..M]表示，则状态表示描述为：
F(v,i)：表示将L的前i个字符划分为以动词结尾（当i<>M时，可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数；
F(u,i)：表示将L的前i个字符划分为以名词结尾（当i<>M时，可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数。
状态转移方程为：
F(v,i)=min{F(u,j)+(0,1)，L(j+1..i)为动词；
F(v,j)+(0,1)，L(j+1..i)为辅词，i<>M；}
F(u,i)=min{F(u,j)+(1,1),L(j+1..i)为名词；
F(v,j)+(0,1),L(j+1..i)为名词；
F(u,j)+(0,1),L(j+1..i)为辅词，i<>M；}
边界条件：F(v,0)=(1,0)；F(u,0)=(∞,∞)；
问题的解为：min{F(v,M),F(u,M)}；方法5：利用四边形不等式的性质降维分析分析猜想证明情形2：i<i’<j<j’
设y=max{p|m[i’,j]=m[i’-1,p]+w[p+1,j]}
z=max{p|m[i,j’]=m[i-1,p]+w[p+1,j’]}
仍需再分两种情形讨论，即z≤y或z>y。
情形2.1，当z≤y<j<j’时：令s[i,j]=k，(i≤j)，最后，我们证明决策s[i,j]满足单调性。
令mk[i,j]=m[i-1,k]+w[k+1,j]；
我们先来证明s[i-1,j]≤s[i,j]，只要证明对于所有i≤k<k’<j且mk’[i-1,j]≤mk[i-1,j]，有：mk’[i,j]≤mk[i,j]。
类似地，我们可以证明一个更强的不等式
mk[i-1,j]-mk’[i-1,j]≤mk[i,j]-mk’[i,j]
mk[i-1,j]+mk’[i,j]≤mk[i,j]+mk’[i-1,j]
利用递推定义式展开整理的：m[i-2,k]+m[i-1,k’]≤m[i-1,k]+m[i-2,k’]，这就是i-2<i-1<k<k’时m的四边形不等式。
我们再来证明s[i,j]≤s[i,j+1]，
设k<k’<j，则我们只需证明一个更强的不等式：
mk[i,j]-mk’[i,j]≤mk[i,j+1]-mk’[i,j+1]
也就是mk[i,j