动态规划(二)

动态规划树形动归与优化方法树形动态规划(皇宫看守)太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。编程任务：帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。数据输入：输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一棵树，描述如下：第1行n，表示树中结点的数目。第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0i=n），在该宫殿安置侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号r1，r2，...，rm。对于一个n（0n=1500）个结点的树，结点标号在1到n之间，且标号不重复。数据输出：输出到OUTPUT.TXT文件中。输出文件仅包含一个数，为所求的最少的经费。输入数据示例输出数据示例25问题分析求给定的带权树的符合下面条件的子顶点集合V：1．若点i∈V，则所有与i相邻的点j可被标号。2．任意一个点j，若j不属于V，则j可被标号。3．S=∑（Weight[i]，i∈V），并且S最小。考虑到树本身的特性：除了根节点外，每一个节点都仅与该节点的父节点与儿子节点有关系；大多数情况下，每个节点的状况都是由它的儿子节点的状况决定的。这与动态规划的无后效性要求相符，再加上本题求的又是最优方案，这一切都与动态规划算法不谋而合。要求覆盖以节点i为顶点的树的最佳方案Vi，显然只需考虑节点i属于或不属于集合V两种情况，两者择优即可。即Vi=min{Vi1，Vi2}（1表示属于，2表示不属于）(一）若i∈V，则对于i的任一儿子j，也只有属于或不属于集合V两种情况：（1）若j∈V，则问题转化到求Vj1的小一级规模问题，转化成功；(2)若j不属于V，则要不求Vj2，要不就是j不能被j的任意一个儿子标号，则求所有Vk（k为j的儿子），Vi1求好了。（二）若i不属于V，i一定要能被i的某个儿子j标号，这时求所有Vj（j为i的儿子）。若所有的j都是j被j的儿子标号时最“省”（即所有Vj=Vj2），那么实际上按这样的方案没有一个j∈V,造成了i不能被标号。这时只要找一个牺牲最小的i的儿子j，把方案Vj2换成Vj1。这样就求出了覆盖以节点i为顶点且不包括节点i的最佳节点集Vi2。状态转移方程通过上面的分析，我们很容易得到下面这组状态转移方程：F(i)=min{F(i,1),F(i,2)}F(i,1)=Weight(i)+∑min{F(j),∑min{F(k,1),F(k,2)}}F(i,2)=∑F(j)；若所有F(j)F(j,1)，则换取代价最小的F(j,2)（以上j为i儿子，k为j儿子）边界条件F(i)=F(i,1)F(i,1)=Weight(i)F(i,2)=+∞（以上i为叶子节点）动态规划模型的建立1、一般动态规划某些问题在状态的选择上会遇到一些困难，但困难更多的集中表现在阶段的划分上，因为阶段的特征并不明显。在这种情况下，通常按状态最优值的大小划分阶段，并采用类似搜索的方法解状态转移方程。双层动态规划农田个数(count.pas)你的老家在河北农村。过年时，你回老家去拜年。你家有一片NM农田，将其看成一个NM的方格矩阵，有些方格是一片水域。你的农村伯伯听说你是学计算机的，给你出了一道题：他问你：这片农田总共包含了多少个不存在水域的正方形农田。两个正方形农田不同必须至少包含下面的两个条件中的一条：边长不相等左上角的方格不是同一方格输入输入数据第一行为两个由空格分开的正整数N、M（1=mn=1000）第2行到第N+1行每行有M个数字（0或1），描述了这一片农田。0表示这个方格为水域，否则为农田（注意：数字之间没有空格，而且每行不会出现空格）输出满足条件的正方形农田个数。样例输入样例输出335110110000分析(1)设F[I，J]表示以方格（I，J）为右下角，可以得到的最大无水正方形边长，那么显然如果（I，J）是水域，F[I，J]=0；否则F[I，J]=Min{F[I-1，J]，F[I，J-1]，F[I-1，J-1]}+1(2)求出了F数组的值后，我们可以用F1[I]表示F数组中，值为I的个数。(3)显然，假定边长为I的正方形数目为Sum[I]，那么有Sum[I]=Sum[I+1]+F1[I](4)最后只要算出Sum数组各个值的和为问题的解。动态规划时间效率的优化一、减少状态总数1、改进状态表示状态的规模与状态表示的方法密切相关，通过改进状态表示减小状态总数是应用较为普遍的一种方法。有一批编号为1至N且尺寸规格一样的箱子。现在要将其中某些箱子叠放起来，使叠放的高度最大，箱子叠放的规则如下：一、每个箱子上最多只能直接叠放一个箱子；二、编号较小的箱子不能放在编号较大的箱子之上；三、每个箱子都给出了自身重量与可承受重量，每个箱子上的所有箱子重量之和不得超过该箱的可承受重量。输入箱子数N（1≤N≤1000）及每个箱子的自身重量与可承受重量，两个数值均为小于等于3000的正整数。输出最多可叠放的箱子总数M和每个箱子的编号。例题3：叠放箱子箱子是按编号顺序叠放，所以可用动态规划求解。设：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]）算法分析上述算法的状态总数为O(n*Total_Weight)，每个状态转移的状态数为O(1)，每次状态转移的时间为O(1)。总时间复杂度=1000*3000=3*106改进一下状态的表示方式，设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。算法优化改进后的算法的时间复杂度是改进前的1/3。但如果在Tot-Weight的值很小，而n的值相当大，前面一种方法更好。对于不同的题目，要从多方面分析，选择适合的最优方法。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,j]ORm[i-1,j-i*k](0≤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,j]ORm[i-1,j-i*k](1≤k≤a[i])当i3时：m[i,j]=m[i,j]ORm[i+1,j-i*k](1≤k≤a[i])规划的边界条件为：m[i,0]=true；0≤i≤7若存在k，使得m[3,k]=true,m[4,Mid-k]=true，则可以实现题目要求，否则无法实现。回顾本题的优化过程可以发现：本题的实际背景与双向搜索的背景十分相似，同样有庞大的状态空间，有确定的初始状态和目标状态，状态量都迅速增长，而且可以实现交汇的判断。从本题的优化过程，我们认识到，双向扩展以减少状态量的方法不仅适用于搜索，同样适用于动态规划。这种在不同解题方法中，寻找共通的属性，从而借用相同的优化思想，可以使我们不断创造出新的方法。动态规划时间效率的优化二、减少每个状态转移的状态数在使用动态规划方法解题时，对当前状态的计算都是进行一些决策并引用相应的已经计算过的状态，这个过程称为“状态转移”。因此，每个状态可能转移的状态数是决定动态规划算法时间复杂度的一个重要因素。动态规划时间效率的优化1、决策量的优化分析问题最优解的性质，缩小决策集合，也可以减少每个状态可能转移的状态数。NOI`96中的添加号问题，是从“所得的和最小”这一原则出发，仅在等分点的附近添加号，从而大大减少了每个状态转移的状态数，降低了算法的时间复杂度。动态规划时间效率的优化添加号问题有一个由数字1，2，...，9组成的数字串（长度不超过200），问如何将M(M=20)个加号(+)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。[输入格式］从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），Ｍ的值在输入文件的第二行行首。[输出格式］在屏幕上输出所求得的最小和的精确值。在一个操场上摆放着一排n（n≤20）堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。例题5：石子归并设n堆石子依次编号为1，2，…..，n。各堆石子数为d[1..n]，则动态规划的状态表示为：m[i,j]，1≤i≤j≤n，表示合并d[i..j]所得到的最大得分，则状态转移方程和边界条件为：m[i,j]=0i=j算法分析jiljkildjkmkimjim]}[],[]1,[{max],[i＜j该算法的时间复杂度为O(n3)。令s[i,j]=k，表示合并的断开位置，可以发现：s[i,j]要么等于i+1，要么等于j。jijimjimjkmkimjki]},,1[],1,[max{]},[]1,[{max于是，状态转移方程优化为：m[i,j]=0i=jM[I，J]=MAX{M[I，J-1]，M[I+1，J]）+}i＜j优化后每个状态转移的状态数减少为O(1)，算法总的时间复杂度也降为O(n2)。jilld][