下载文档原格式
第6章 动态规划动态规划（Dynamic Programming ）是解决多阶段决策过程最优化的一种有用的数学方法。
它是由美国学者Richard .Bellman 在1951年提出的，1957年他的专著《动态规划》一书问世，标志着运筹学的一个重要分支－动态规划的诞生.动态规划也是一种将多变量问题转化为单变量问题的一种方法。
在动态规划中，把困难的多阶段决策问题变换成一系列相互联系的比较容易的单阶段问题一个个地求解。
动态规划是考察解决问题的一种途径 ,而不是一种特殊的算法，不像线性规划那样有统一的数学模型和算法（如单纯形法）.事实上，在运用其解决问题的过程中还需要运用其它的优化算法。
因此，动态规划不像其它方法局限于解决某一类问题,它可以解决各类多阶段决策问题。
动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。
在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。
许多规划问题用动态规划的方法来处理,常比线性规划或非线性规划更有效。
特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。
动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。
本教材主要介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用。
6.1动态规划的基本理论6.1.1多阶段决策过程的数学描述有这样一类活动过程,其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策,以使整个过程达到最佳的活动效果。
任何一个阶段(stage ，即决策点)都是由输入(input ）、决策（decision ）、状态转移律（transformation function )和输出(output )构成的，如图6-1（a ）所示.其中输入和输出也称为状态(state ）,输入称为输入状态，输出称为输出状态。
第三章：动态规划3.1 动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。
即决策过程可划分为明显的阶段。
二、什么叫动态规划(D.P.–Dynamic Program)：多阶段决策问题最优化的一种方法。
广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。
三、动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著《动态规划》于1957年出版。
四、动态决策问题分类：1、按数据给出的形式分为：•离散型动态决策问题。
•连续型动态决策问题。
2、按决策过程演变的性质分为：•确定型动态决策问题。
•随机型动态决策问题。
五1、阶段(stage)n ：作出决策的若干轮次。
n = 1、2、3、4、5。
2、状态(state)S n ：每一阶段的出发位置。
构成状态集，记为S nS 1={A}，S 2={B 1,B 2,B 3}，S 3={C 1,C 2,C 3}，S 4={D 1,D 2,D 3}，S 5={E 1,E 2}。
阶段的起点。
3、决策(decision)X n ：从一个阶段某状态演变到下一个阶段某状态的选择。
构成决策集，记为D n (S n )。
阶段的终点。
D 1(S 1)={X 1(A)}={B 1,B 2,B 3}= S 2，D 2(S 2)={X 2(B 1),X 2(B 2),X 2(B 3)}={C 1,C 2,C 3}=S 3，D 3(S 3)={X 3(C 1),X 3(C 2),X 3(C 3)}={D 1,D 2,D 3}=S 4，D 4(S 4)={X 4(D 1),X 4(D 2),X 4(D 3)}={E 1,E 2}=S 5D 5(S 5)={X 5(E 1),X 5(E 2)}={F;F}={F}。
4、策略(policy)：全过程中各个阶段的决策Xn 组成的有序总体{Xn }。
如 A àB2àC1àD1àE2àF5、子策略(sub-policy)：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。
一、1050 To the Max：这是我的第一个DP，题目的意思很简单，在一个矩阵里面找它的子矩阵，使得子矩阵数值之和到达最大。
其实就是最大子段和问题在二维空间上的推广。
先说一下一维的情况吧。
设有数组a0,a1…an,找除其中连续的子段，使它们的和达到最大。
最开始的想法，是枚举矩阵的长度，计算每个子矩阵的和，然后比较得出最大值，这样要消耗的时间为O(n)。
让我们再想想，如果这个序列的每一个数都是整数，那么它们的最大子段和就是把所有的数相加。
所以我们想要尽可能多地找到正数相加。
在序列中有负数的情况下，从头开始扫描数组，把正数都相加，这其中可能会有负数，一种情况是：负数和减小子段和，但这时子段和仍然为正，用sum记录下连续子段和的最大值，继续想后扫描，因为后面有可能出现更大的正数的情况，会使和比原来没加负数之前更大；第二种情况是：加入一个负数后，是这个连续的子段和的值变成了负数，这时就要抛弃该负数以及该负数之前的所有序列，因为前面若有子段与后面构成了连续的子段，则这个子段一定会包括这个负数，而在这个负数之前的序列的和是个负数，那么这个子段的和一定不是最大的子段和。
抛弃这个负数之前的序列后，子段和从这个负数后面的第一个数算起，继续扫描。
//一维数组求最大字段int submax1(int a[], int n){int b=0;int bn=-32767;int i;int sum=0;for(i=0; i<n; i++){if(b>0){b+=a[i];}else if(a[i]>bn && a[i]<0){bn=a[i];b=a[i];}else{b=a[i];}if(b>sum){sum=b;}}if(sum==0)return bn;elsereturn sum;}其中变量b就是记录当前扫描过的子段和的，而sum记录的是子段和的最大值二维的情况：这里我使用了一个很简单的做法，在二维数组a[i][j]里面枚举第一维的长度k，然后得到一个k*n的子矩阵，把这个子矩阵的每一列数值相加，就把这个二维数组转化成了一维，再调用函数int submax1(int a[], int n)，就计算得出最大值。
总结：感觉我做这道题目还不是很像DP，只有在求一维情况下的sum记录最大值，以及在扫描是计算的子段和b，代表了某数前面连续的最大子段和。
二、1579 Function Run Fun这肯定是一个处心积虑的函数，没看出它有什么实际的用处Consider a three-parameter recursive function w(a, b, c):if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 这本身就是一个递归函数，要是按照函数本身写递归式，结果肯定是TLE，这里我开了一个三维数组，从w(0,0,0)开始递推，逐步产生到w(20,20,20)的值，复杂度O(n^3) 总结：这道题是很地道的DP，因为它的子问题实在是太多了，但还是属于简单题目的范畴，就像把fabonacci函数增加到三维，限制条件多点而已，而实际上的做法都一样。
三、1080 Humman Gene Function应该说这是一道比较经典的DP，两串基因序列包含A、C、G、T，每两个字母间的匹配都会产生一个相似值，求基因序列（字符串）匹配的最大值。
感觉这题有点像求最长公共子序列。
只不过把求最大长度改成了求最大的匹配值。
用二维数组m[i][j]记录字符串a中的第i个字符与字符串b中的第j个字符匹配所产生的最大值。
若字符串a的长度为la，字符串b的长度为lb，初始时m[la][k](0<=k<=lb-1),这里即为字符串a的末尾与b中的字符匹配，因为超过了字符串a的长度，所以匹配的时候只能时以空格’-’匹配。
同理可产生m[k][lb](0<=k<=la-1)，的所有值，再以此往前递推，其状态转移方程为m[i][j]=max{map[i][j]+m[i+1][j+1],m[‘-‘][j]+m[i][j+1],m[i][‘-’]+m[i+1][j]}所以最后m[0][0]即为所求。
四、2533 Longest Ordered Subsequence很早以前就看过这题，求最大递增序列，那时刚刚晓得什么叫“动态规划”，是《算法设计与分析》（王晓东）上的一道习题，开始不会做。
后来想了一种很笨的办法，用了O(n^2)的时间，还附加了n^2的空间。
看了世铭的两种方法，一种是O(n^2),一种是O(nlogn)。
两种方法核心的方法都一样，用一个n大小的一维空间(a[n])，a[i]表示子串长度为i时所有子串最大值中的最小值，因为要找一个i长度的子串，那么a[i]的值至少要比长度为i-1子串中的一个最末位的值要大。
之所以会有两种时间复杂度的差别，就是在查找i-1长度的末尾值中的最小值的时候，前者是线性的搜索，后者是用的二分搜索，提高了时间效率。
另外说一下这题的变形吧，1631 Briging signals，是有很多路由器搭线，要求求出互不相交的搭配的最大个数。
细细分析一下题目，只要被匹配的路由器序号是一个递增的序列，则他们的连线就不会相交，就把这题转化为求最大递增序列的问题。
但需要注意的是这题的问题规模n 达到了40000，Time Limit :1000MS，所以在这里要选用刚才提到的O(nlogn)的算法，才不会导致TLE。
五、1014 Dividing实际上早就看到这题了，那时对ACM的认识还很幼稚，刚学完程序设计，学会怎么用递归，也不看题目的条件，反正就是六种marble，写了个递归的程序，测试数据当然能通过，但其结果肯定是TLE了。
又过了一段时间，有了点时间效率的观念，写了个枚举法计算总和的1/2的可达性，不过还是有很多情况我都没有考虑到，结果WA了。
到现在学DP，再来看想想这题，其实还有更好的解法。
也是计算总和的1/2(sum)的可达性，如果marble的总数是n，则DP算法的时间复杂度可以达到O(n*sum)。
用一个一维数组标记从0－sum所有加和的可达性，对于一颗宝石的价值i，数组a[j]==true，表示和为j可达，那么可得出a[i+j]=true,即i+j的值可达。
循环以致于用完所有的宝石，观察a[sum]的值，true即为这些宝石可分，反之不可分。
六、2192 Zipper又是一道字符串的动态规划题目，简述一下：给出三个字符串，s1,s2,s3，s3的长度为s1与s2长度之和，判断s1，s2是否为s3的不重合的公共子序列。
其实就是判别公共之序列的升级版，把原来的一对一，改成了一对二。
我用一个二维数组mark[i][j]记录s1中的第i个字符以及s2中的第j个字符能否与s3[i+j]想匹配。
If(s1[i]==s3[i+j]) mark[i+1][j]=true;//s1中的第i个字符匹配，则s1串向后移一个字符If(s2[j]==s3[i+j]) mark[i][j+1]=true;//s2中的第j个字符匹配，则s2串向后移一个字符这样用O(n^2)的时间，递推能产生mark[c1][c2]的值，值为true输出即能够全部匹配。
七、2576 Tug of War我觉得非常有必要做的一道题目。
这道题目看似很简单，实质就是n个数，将其分成两堆，两堆数量的差距不超过1，并且使这两堆数字之和最接近。
是一道动态规划题目，看起来简单是因为受了1014题的影响，但这题两堆的数目是确定的，一堆是n/2个，另一堆则是n-n/2个,而1014题是不受加和数目的影响的。
这题也不同与多米勒骨牌那题，因为那题中各个数字之间是一一对应的。
苦想了一天没有结果，看来这题还要寻求其它的方法。
这题不是我自己想除来的，看了alpc02的代码，自己又照自己的理解重写了一遍。
记录状态是用一个二维数组，mark[i][j]表示i个数相加，其值能否达到j，如果能mark[i][j]的为true。
对于一个输入的数w，修改i个数的每一种状态，其状态转移方程：If(m[i][j]) then m[i][j+w]=true;//j+w的值可由j的值加得由后往前修改每一个i下的可达值。
那么最后就只要再n/2行中找出m[n/2][j]的最大值（j<=total/2），这就是两堆之和最接近的一组数值。
八、2441 Arrange the Bulls这题里我看到了动态规划的一种新的方法。
每头牛有自己喜欢的篮球场，我们的任务就是安排这些牛到它们喜欢的篮球场去，然后计算所有合理的解的数量（篮球场的数目最多20个）。
显然，要找到一个解，很容易就能搜出，但是要求所有解的数量，如果再用搜索的方法，在时间上是不堪忍受的。
这里用了一种新的方法（对于我来说是一种新方法^_^）。
用二进制数记录当前篮球场使用的状态，“1”表示未分配，“0”表示已分配，每个篮球场与每个数位相对应。
所以20个篮球场就总共需要一个1<<20的数组来记录所有生成的状态。
想到这里，我觉得这题基本上已经解决一半了，剩下的就是如何进行状态转移，用的就是二进制运算。
我觉得我在这个方面一点都不熟悉，不会写，看了别人的代码，然后自己仿写了。
一种是用滚动数组，这种方法占用时间空间都较大，另一种是状态压缩的DP，方法比较巧妙。
呵呵，要讲得更深点，等我变成牛人在续吧……九、2738 Two Ends有点想博弈的题目，我事用dp来做的。
有一组数，两个人分别轮流从数组两头取数，第一个取数的人可以选用任意的策略，第二个人则要一直使用贪心策略。
问最后第一个人所取得的数字之和比第二个人取得的数字之和最多多多少。
很容易想到DP，第二个人的取数规则是一定的，只有第一个个人可以选择，那么在第一个人取数的时候就有状态转移方程，dp[i][j]表示前面是第i个数后面是第j个数的时候第一个人所能得到数字和的最大值。
if(dp[i][j]+a[i]>dp[i+1][j])dp[i+1][j]=dp[i][j]+a[i]; //取前面的数if(dp[i][j]+a[j]>dp[i][j-1])dp[i][j-1]=dp[i][j]+a[j]; //取后面的数那么第二个人的状态转移就相对比较好确定了：if(a[i]<a[j] && dp[i][j]!=-1 && dp[i][j]>dp[i][j-1])dp[i][j-1]=dp[i][j];if(a[i]>=a[j] && dp[i][j]!=-1 && dp[i][j]>dp[i+1][j])dp[i+1][j]=dp[i][j];最后一步只需比较dp[i][i]的值，选其中最大的出来就行了^_^十、2411 Mondriaan's Dream一道状态压缩的DP题。
