动态规划学习课件.ppt

改进后的算法的时间复杂度是改进前的1/3。但如果在Tot-Weight的值很小，而n的值相当大，前面一种方法更好。对于不同的题目，要从多方面分析，选择适合的最优方法。 * [问题描述] 现有n首由Raucous Rockers 演唱组录制的歌曲，计划从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择： ?? (1) 这组唱片中的歌曲必须按照它们创作的顺序排序； (2) 包含歌曲的总数尽可能多。 输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。 Raucous Rockers 演唱组 * 设n首歌曲按照创作顺序排序后的长度为long[1..n]，则动态规划的状态表示描述为： g[i, j, k]，(0≤i≤n，0≤j≤m，0≤kt), 表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目。 * 规划的边界条件为： 当0≤j≤m， 0≤kt时：g[0,j,k]=0; 问题的最优解为：g[n,m,0]。 状态转移方程为： 当k≥long[i]，i≥1时： g[i, j, k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]} 当klong[i]，i≥1时： g[i, j, k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]} * 改进的状态表示描述为： 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]; * 算法的时间复杂度为：O(n2)。 规划的边界条件： 当0≤i≤n时，g[i,0]=(0,0) 题目所求的最大值是： answer=max{k| g[n, k]≤(m-1,t)} * 2、选择适当的规划方向 规划方向的选择主要有两种：顺推和逆推。若初始状态确定，目标状态不确定，则应考虑采用顺推，反之，若目标状态确定，而初始状态不确定，就应该考虑采用逆推。那么，若是初始状态和目标状态都已确定，可以选用双向规划。 动态规划时间效率的优化 * 双向规划与双向有哪些信誉好的足球投注网站的主要思想类似：在状态空间十分庞大，而初始状态和目标状态又都已确定，为了减少状态的规模，分别从初始状态和目标状态两个方向进行扩展，并在两者的交汇处得到问题的解。 * 例题4：Divide (Merc`2000) 有价值分别为1..6的大理石各a[1..6]块，现要将它们分成两部分，使得两部分价值和相等，问是否可以实现。其中大理石的总数不超过20000。 动态规划时间效率的优化 * 令S=∑(i*a[i])，若S为奇数，则不可能实现，否则令Mid=S/2， 问题转化为能否从给定的数中中选取部分数，使其和为Mid。 设m[i, j]表示能否从价值为1..i的大理石中选出部分大理石， 使其价值和为j，若能，则用true表示，否则用false表示。 则状态转移方程为： m[i, j]=m[i-1, j] OR m[i-1,j-i*k] (1≤k≤a[i]) 规划的边界条件为：m[i,0]=true； 0≤i≤6 若m[i, Mid]=true，0≤i≤6，则可以实现题目要求，否则不可 能实现。 算法分析 * 上述算法每个状态转移的状态数为a[i]，每次状态转移的时间为O(1)，状态总数是所有值为true的状态的总数。 * 本题在i较小时，值为true的状态也较少，但随着i的增大， 值为true的状态也急剧增多，影响了算法的时间效率。 我们分别求出从价值为1..3的大理石中选出部分大理石所能 获得的所有价值和，和从价值为4..6的大理石中选出部分大 理石所能获得的所有价值和。再判断是否存在和为Mid的价 值和，从而得出问题的解。 算法优化 * 状态转移方程改进为： 当i≤3时：m[i, j]=m[i-1, j] OR m[i-1,j-i*k] (1≤k≤a[i]) 当i3时：m[i, j]=m[i+