动态规划及其应用.ppt

1、动态规划及其应用,赖国堃 福建师大附中,基本概念,动态规划问题的满足两个基本性质 一、最优子结构 问题可以表示为一些子问题，然后通过求解子问题的最优答案，得到问题答案。 二、无后效性 当前决策不会影响到之后的决策。,动态规划的3个基本要素,状态 转移 边界 这3个一般是做动态规划时要先思考清楚的问题。,例题,例1、数字三角形 （图2）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 每一步可沿左斜线向下或右斜线向下走； 1三角形行数100； 三角形中的数字为整数0，1，99； 输入数据： 由INPUT.TXT文件中首先读到的是三角形的行数。 在

2、例子中INPUT.TXT表示如下： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出数据： 把最大总和（整数）写入OUTPUT.TXT文件。 上例为： 30,分析,只要对该题稍加分析，就可以得出一个结论： 如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。 我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺序求出第一阶段、第二阶段，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终

3、点的最佳路径。,状态：fI,j表示，走到第i行第j列最大得分 转移：fI,j=fi-1,j-1+cI,j(j1) =fI-1,j+cI,j(ji),For i := 2 to N Do For j := 1 to i Do Begin Listi, j.Tot := -1; 从1,1至i,j的数字和初始化 If (j 1) And (Listi - 1, j - 1.Tot + Listi, j.Val Listi, j.Tot) Then Listi, j.Tot := Listi - 1, j - 1.Tot + Listi, j.Val; 若从i-1,j-1选择右斜线向下会使1,1至i,

4、j的数字和最 大,则决策该步 If (j i) And (Listi - 1, j.Tot + Listi, j.Val Listi, j.Tot) Then Listi, j.Tot := Listi - 1, j.Tot + Listi, j.Val 若从i-1,j选择左斜线向下会使1,1至i,j的数字和最大,则决策该步 End; for,例题,有一个体积为V背包，现在有n个物品，他们格子有自己的体积vi，和各自的价值wi。现在需要选出一些物品装进背包，你的任务是使装进物品的价值最大。,状态：fI,j(i表示处理第几个物品，j表示已用了多大空间) 转移：fI,j=max(fi-1,j-vi

5、+ci,fi-1,j) 边界：f0,0=0;,for i:=1 to n do for j:=1 to m do begin if j=vi then fi,j:=max(fi-1,j-vi+ci,fi-1,j) else fi,j:=fi-1,j; end;,例题,【问题描述】 假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V 是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F 的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序

6、即如果I J，则花束I 必须放在花束J左边的花瓶中。 例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。,每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时会产生不同的美学效果，并以美学值(一个整数)来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示。比如杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。

7、,为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1F100，FV100，50AIJ50，其中AII是花束I摆放在花瓶J中的美学值。输入整数F，V 和矩阵(AIJ)，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。,【输入文件】 第一行包含两个数：F，V。 随后的F 行中，每行包含V 个整数，Aij 即为输入文件中第（i+1 ）行中的第j 个数 【输出文件】 包含两行:第一行是程序所产生摆放方式的美学值。第二行必须用F 个数表示摆放方式，即该行的第K个数表示花束K所在的花瓶的编号。

8、 【输入样例】 3 5 7 23 5 24 16 5 21 -4 10 23 -21 5 -4 -20 20 【输出样例】 53 2 4 5,方法1,既然要拿花束一个一个的放，我们就以花束划分阶段。在这里，阶段变量k表示的就是要布置的花束数目（前k束花），状态变量sk表示第k束花所在的花瓶。而对于每一个状态sk，决策就是第k-1束花应该放在哪个花瓶，用uk表示。最优指标函数fk(sk)表示前k束花，其中第k束插在第sk个花瓶中，所能取得的最大美学值。,规划方程为： （其中A(i,j)是花束i插在花瓶j中的美学值） fI,j=max(fi-1,u+aI,j)(i=uj),方法2,以花瓶的数目来划

9、分阶段。在这里阶段变量k表示的是要占用的花瓶数目（前k个花瓶），状态变量sk表示前k个花瓶中放了多少花。而对于任意一个状态sk，决策就是第sk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(sk)表示前k个花瓶中插了sk束花，所能取得的最大美学值。 规划方程为：fI,j=max(fi-1,j,fi-1,j-1+aj,i),区间类动态规划,（1）石子合并 【问题描述】 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将n堆石子合并成一堆的最小得分和

10、最大得分。 【输入文件】包含两行，第1 行是正整数n（1=n=100），表示有n堆石子。第2行有n个数，分别表示每堆石子的个数。 【输出文件】输出两行。 第1 行中的数是最小得分；第2 行中的数是最大得分。 【输入样例】44 4 9 5 【输出样例】4354,分析 看到本题，容易想到使用贪心法，即每次选取相邻最大或最小的两堆石子合并。 然而这样做对不对呢？看一个例子。 6 3 4 6 5 4 2 如果使用贪心法求最小得分，应该是如下的合并步骤： 第一次合并 3 4 6 5 4 2 2,3合并得分是 第二次合并 5 4 6 5 4 5,4合并得分是9 第三次合并 9 6 5 4 5,4合并得分是

11、9 第四次合并 9 6 9 9,6合并得分是15 第五次合并 15 9 15,9合并得分是24 总得分599152462但是如果采用如下合并方法，却可以得到比上面得分更少的方法： 第一次合并 3 4 6 5 4 2 3,4合并得分是7 第二次合并 7 6 5 4 2 7,6合并得分是13 第三次合并 13 5 4 2 4,2合并得分是6 第四次合并 13 5 6 5,6合并得分是11 第五次合并 13 11 13,11合并得分是24 总得分7136112461 显然，贪心法是错误的。 为什么？ 显然，贪心只能导致局部的最优，而局部最优并不导致全局最优。,具体来说我们应该定义一个数组si,j用来

12、表示合并方法，i表示从编号为第i堆的石头开始合并，j表示从i开始数j堆进行合并，si,j为合并的最优得分。 则动规方程为： SI,j=minsI,k+si+k,j-k+sumI,j 1=k=j-1 2=j=n 边界：sI,1=0;,由此得到算法框架如下： For j2 to n do 枚举阶段，从两两合并开始计算 For i1 to n do 计算当前阶段的n种不同状态的值 For k1 to j-1 do 枚举不同的分段方法 begin If i+kn then t(i+k) mod n else ti+k 最后一个连第一个的情况处理 si,j最优si,k+st,j-k+sum1,3 sum

13、i,j表示从i开始数j个数的和 end;,在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。 需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得

14、到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为： (41)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 (41)2)3）=10*2*3+10*3*5+10*5*10=710。,【输入文件】 输入文件energy.in的第一行是一个正整数N（4N100），表示项链上珠子

15、的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当i时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。 【输出文件】 输出文件energy.out只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。 【输入样例】 4 23510 【输出样例】 710,算法分析,如果要求一个链的最优合并方式,可以把这个链从中间断开,枚举断开处,分别求出2段的

16、最优合并的值,再将这两端合并,而这条链断开后的2段的最优合并方式也可以用同样的方式计算,因此,本题具有最优子结构性质,可以用动态规划求解 但本题中并不是一个链而是一个环,但这并不影响最优子结构性质,可以做一条链,长度是环的2倍,其中前半段与后半段一样,都为环的顺序(可任意确定),那么,从中间任取长度为n的一段,就实现了环的性质首尾相接,设fk,j为从珠子k到珠子j的最优合并,那么枚举断开点p,则fk,j的最优值为fk,p的最优值和fp+1,j的最优值的和再加珠子k,p和p+1,j合并的值vk(k的头标记)*vp+1(p的尾标记=p+1的头标记)*vj+1(即j的尾标记) 动规方程为:fk,j=

17、maxfk,p+fp+1,j+vk*vp+1*vj+1 (kj2*n且k=pj),for d=1 to n /从小到大枚举链的长度 for k=1 to 2*n do /枚举链的起点 begin j=k+d-1;/计算链的终点 if(j=2*n)/若在最大值范围内 for p=k to j-1 /枚举断开点begin 根据方程更新fk,j的值;end;end;,例题,1、加分二叉树（noip2003） 【问题描述】 设一个n个节点的二叉树tree的中序遍历为（l,2,3,n），其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树

18、都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分 subtree的右子树的加分subtree的根的分数 若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树tree。要求输出； （1）tree的最高加分 （2）tree的前序遍历,【输入格式】 第1行：一个整数n（n30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数100）。 【输出格式】 第1行：一个整数，为最高加分（结果不会超过4,000,000,000）。 第2行：

19、n个用空格隔开的整数，为该树的前序遍历。 【输入样例】 5 5 7 1 2 10 【输出样例】 145 3 1 2 4 5,如果整棵树的权值最大，必然有左子树的权值最大，右子树的权值也最大，符合最优性原理 本题适合用动态规划来解。如果用数组fi,j表示从节点i到节点j所组成的二叉树的最大加分，枚举根节点，则动态方程可以表示如下： fi,j=maxi=t=j | dt+fi,t-1*ft+1,j 初始： f(i,i)=di 目标：f(1,n),procedure dfs(l,r:integer); var i:integer; s:int64; begin if fl,r0 then exit;

20、/实现记忆化 if l=r then /处理边界 begin fl,r:=al; dl,r:=l; exit; end;,for i:=l to r do begin s:=0; if i-l0 then begin dfs(l,i-1);s:=fl,i-1;end;/处理左子树的加分 if r-i0 then begin dfs(i+1,r);if s0 then s:=s*fi+1,r else s:=fi+1,r;end; inc(s,ai); if sfl,r then begin fl,r:=s; dl,r:=i; end; end; end;,树形动态规划,顾名思义，树型动态规划就

21、是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向： 1、根叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。 2、叶根：既把根的子节点传递有用的信息给根，完成后根得出最优解的过程。这类的习题比较的多，下面就介绍一些这类题目和它们的一般解法。（树的后序遍历求解）,2、Ural 1018二叉苹果树 【问题描述】 有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵

22、树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树 2 5 / 3 4 / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。 输入格式 第1行2个数，N和Q(1=Q= N,1N=100)。 N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。 每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。 每根树枝上的苹果不超过30000个。 输出格式 一个数，最多能留住的苹果的数量。,样例输入 5

23、21 3 11 4 102 3 203 5 20 样例输出 21,分析： 因为题目一给出就是纯二叉的树结构，如果要保留住最多苹果数量，必然是左子树保留尽量多，右子树也保留尽量多，满足最优性原理,我们定义状态,fi,j表示以i为根的子树(还包括 i与 i的父亲 这条边)内,保存j条边最多可以有多少苹果,显然fi,j=max(flefti,k+frighti,j-k-1)+applei,fatheri; （0=k=j-1） 边界：f0,i=0;fi,0=0; 问题的解：f1,q+1;虚拟了一条边，也就相当于多添加了一个节点1的父亲节点，这条边为1和它父亲节点的,procedure tree_dp(

24、t,k:integer); var i,ls,rs:integer; begin if ft,k0 then exit; if (t=0) or (k=0) then begin ft,k:=0; exit; end; ft,k:=0; for i:=0 to k-1 do begin tree_dp(treet.lc,i);/左子树 tree_dp(treet.rc,k-i-1);/右子树 ls:=ftreet.lc,i;/记录左子树的值 rs:=ftreet.rc,k-i-1;/记录右子树的值 if ft,kls+rs then ft,k:=ls+rs;/比较 end; ft,k:=ft,

25、k+treet.s; /保存最优值 end;,例题,问题描述 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？ 输入： 第一行有两个整数N,M用空格隔开。(1=N=200,1=M=150) 接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示

26、没有直接先修课（1=ki=N, 1=si=20）。 输出： 只有一行，选M门课程的最大得分。,样例：,分析,根据先修关系，选修的课程组成了一个森林，我们虚拟一个根节点0作为这棵森林的总根 然后我们把一棵普通树转化为二叉树进行求解。 读入数据时把二叉树建好：第一个孩子作为父节点的左子树，其它孩子作为第一个孩子的右子树。 F（i，j）：表示节点以i为根结点取j门课的最高学分，则,F(leftc,k)：表示左子树选了k门课的最大学分。 F(rightc,j)：表示右子树选了j门课的最大学分。 Fleftc,k+frightc,j-k-1+si：表示左子树选了k门，当然选了左子树，必须选根，右子树选了

27、j-k-1门。 其实是四种情况决策：(1) 选右子树中j门（2）选左子树（j-1）门+根 （3）选右子树（j-1门）+根 （4）选左子树（k门）+根+选右子树（j-k-1） 程序中节点1表示空节点，0是根节点，1n是n门可选课程的节点.,源程序代码： program bluewater; type tree=record l,r,k:longint; end; var s:string; i,j,k,l:longint; n,m:longint; a:array0.200 of tree;/存储树的信息 b:array-1.200,0.150 of integer;/状态表示 f:array0

28、.200 of longint;/存父亲节点,procedure treedp(x,y:longint); var i,j,k,l:longint; begin if bx,y=0 then exit; treedp(ax.r,y);只有右子树的情况 j:=bax.r,y; for k:=1 to y do左右子树都有的情况 begin treedp(ax.l,k-1); treedp(ax.r,y-k); i:=bax.l,k-1+bax.r,y-k+ax.k; if ij then j:=i; end; bx,y:=j; end;,begin readln(s); assign(input

29、,s);reset(input); readln(n,m); fillchar(f,sizeof(f),0); for i:=0 to n do begin ai.l:=-1;ai.r:=-1;ai.k:=-1;end; 建树 for i:=1 to n do begin readln(k,l); ai.k:=l; if fk=0 then ak.l:=i else afk.r:=i; fk:=i; end;,边界 for i:=-1 to n do for j:=-1 to m do if (i=-1) or (j=0) then bi,j:=0 else bi,j:=-1; 记忆化实现动规

30、 treedp(a0.l,m); 输出 writeln(ba0.l,m); end. 时间复杂度最大为O(n3) 思考:若本题加上选那些课程可得到这个最大学分,怎样修改程序？,4、 河流(IOI2005) 一颗有N+1个结点的树，树中的每个结点可能会生产出一些产品。这些产品要么就地加工（要有加工厂才行），要么运送到它的父亲结点那儿去。现在在整棵树的根结点处已经有了一个产品加工厂，而且所有的产品最终必须在某个加工厂加工才行。由于运费昂贵，不可能将所有的产品都运送到根节点处加工。现在决定在树中的某些结点新增总共K个加工厂，现在要你选择这K个加工厂的厂址。 假设结点i会生产出Wi吨产品，它的父结点是

31、Pi。而它到它的父结点的路径的长度是Ui。运费的计算是每运送1顿的货物，每单位长度收取1的费用。根节点的编号为0。,例如下图，0节点是根节点，如果要新增两个工厂，最佳方案是建在2、3两个节点上，这样总的费用为： 1*1（1号）+1*3（4号）=4,分析：由于题目中给出的树是多叉树，不便于进行动态规划。我们先利用儿子兄弟表示法，将多叉树转化为二叉树 进行了相关的转化之后，设f(i,j,k)表示在新树中，以i结点为根的子树中，分配k个加工厂。并且离i结点最近的加工厂在j结点的情况下。i结点及其子树内的所有产品，加工所需要的费用。 转移方程很容易就可以写出来： 总时间复杂度为O(N2K2)。,状态压

32、缩动态规划,有一些问题却被认为很可能不存在有效的(多项式级的)算法，这里以对几个例题的剖析，简述状态压缩思想及其应用。,预备知识,引例,在n*n(n20)的方格棋盘上放置n个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。,分析,其实本题是一个简单的组合数学问题，因为每行有且仅有一个车，所以我们只要来考虑每行上列的问题，显然每列只能出现一次，这题答案就是n的一个全排列，为 P(n,n)=n! 当然这题还有状态压缩的解法。,分析,我们仍然一行一行放置。 取棋子的放置情况作为状态，某一列如果已经放置棋子则为1，否则为0。这样，一个状态就可以用一个最多20位的二进制数表示。 例如n=5,第

33、1、3、4列已经放置，则这个状态可以表示为01101(从右到左)。设fs为达到状态s的方案数，则可以尝试建立f的递推关系。,前两行在第3、4列放置了棋子(不考虑顺序，下同)，第三行在第1列放置； 前两行在第1、4列放置了棋子，第三行在第3列放置； 前两行在第1、3列放置了棋子，第三行在第4列放置。,这三种情况互不相交，且只可能有这三种情况，根据加法原理，fs应该等于这三种情况的和。 根据上面的讨论思路推广之，得到引例的解决办法： 其中s的右起第i+1位为1 (其实就是在枚举s的二进制表示中的1),状态压缩具有良好的拓展性。 在n*n(n20)的方格棋盘上放置n个车，某些格子不能放，求使它们不能

34、互相攻击的方案总数。 我们只需要在原题的程序中枚举添加1的位置的时候进行判断就行。,program p1; const max=1 shl 20; var n,i,t,c,j,tmp,r:longint; f,a:array0.maxof int64; begin assign(input,p1.in);a reset(input); readln(n); fillchar(f,sizeof(f),0); for i:=1 to n do /读入及预处理 begin ai:=0; for j:=1 to n do /如果第i行的某位为0,表示这位不能放置 begin read(c); ai:=ai shl 1; if c=1 then ai:=ai+1; end; end;,f0:=1; for i:=1 to (1 shl n)-1 do begin t:=i; r:=0; while t0 do /计算状态i中1的个数，即可得到其为第几行 begin inc(r); t:=t-(t and -t); end; tmp:=i and ar