动态规划的模型构建与优化方法.ppt

动态规划模型构建与优化综述分析思路什么是动态规划？多阶段决策问题取石子游戏分析分析什么是动态规划？动态规划的核心——记忆化记忆化搜索与动态规划记忆化搜索与动态规划例题一（线性规划模型）对例一的优化例题二（区间模型）解法继续序列压缩算法一算法二最长公共子串问题（lcs)分析拓展例子例子的扩展决策变量满足单调性问题矩阵处理类动态规划模型分析矩阵类规划模型分析双层规划模型树形动态规划例题分析转移优化例题：珠宝（gems）分析动态规划时间效率的优化有一批编号为1至N且尺寸规格一样的箱子。现在要将其中某些箱子叠放起来，使叠放的高度最大，箱子叠放的规则如下：
一、每个箱子上最多只能直接叠放一个箱子；
二、编号较小的箱子不能放在编号较大的箱子之上；
三、每个箱子都给出了自身重量与可承受重量，每个箱子上的所有箱子重量之和不得超过该箱的可承受重量。
输入箱子数N（1≤N≤1000）及每个箱子的自身重量与可承受重量，两个数值均为小于等于3000的正整数。输出最多可叠放的箱子总数M和每个箱子的编号。箱子是按编号顺序叠放，所以可用动态规划求解。设：
Weight[I]表示第I个箱子的重量。
Support[I]表示第I个箱子的承受重量。
F(i,j)表示前i个箱子中最多可选出f(i,j)个叠放，最底层承受的重量为j。
F(i,j)=Max{F(i-1,j+Weight[i])+1,F(i-1,j)}。
（其中，J<=support[I]）
改进一下状态的表示方式，设F[I，j]表示前i个箱子叠放j个箱子(从上往下，按编号从大到小的顺序叠放)时可承受的最小重量。
F[i，j]：=Min{F[i-1，j]，F[i-1，j-1]+Weight[i]}
Ans：=Max（J|F[i，j]）（F[i，j]〈=support[i]〉）

上述算法的状态总数为O(n*n)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)，所以总的时间复杂度=1000*1000=1*10^6。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]ORm[i-1,j-i*k](1≤k≤a[i])
规划的边界条件为：m[i,0]=true；0≤i≤6
若m[i,Mid]=true，0≤i≤6，则可以实现题目要求，否则不可
能实现。
本题在i较小时，值为true的状态也较少，但随着i的增大，
值为true的状态也急剧增多，影响了算法的时间效率。

我们分别求出从价值为1..3的大理石中选出部分大理石所能
获得的所有价值和，和从价值为4..6的大理石中选出部分大
理石所能获得的所有价值和。再判断是否存在和为Mid的价
值和，从而得出问题的解。

回顾本题的优化过程可以发现：本题的实际背景与双向搜
索的背景十分相似，同样有庞大的状态空间，有确定的初始
状态和目标状态，状态量都迅速增长，而且可以实现交汇的
判断。
从本题的优化过程，我们认识到，双向扩展以减少状态
量的方法不仅适用于搜索，同样适用于动态规划。这种在不
同解题方法中，寻找共通的属性，从而借用相同的优化思想，
可以使我们不断创造出新的方法。
二、减少每个状态转移的状态数
在使用动态规划方法解题时，对当前状态
的计算都是进行一些决策并引用相应的已经计算过
的状态，这个过程称为“状态转移”。因此，每个状
态可能转移的状态数是决定动态规划算法时间复杂度
的一个重要因素。1、决策量的优化
分析问题最优解的性质，缩小决策集合，也
可以减少每个状态可能转移的状态数。

NOI`96中的添加号问题，是从“所得的和最小”
这一原则出发，仅在等分点的附近添加号，从而
大大减少了每个状态转移的状态数，降低了算法
的时间复杂度。添加号问题在一个操场上摆放着一排n（n≤20）堆石
子。现要将石子有次序地合并成一堆。规定
每次只能选相邻的2堆石子合并成新的一堆，
并将新的一堆石子数记为该次合并的得分。

试编程求出将n堆石子合并成一堆的最小
得分和最大得分以及相应的合并方案。设n堆石