文档介绍：动态规划入门篇成都大学第二期ACM暑期集训李明金2009/08/12马健鸿2010/08/112009-8-12成都大学ACM暑期集训DP篇——李明金*前言纵观ACM届,大到每年的全球总决赛,小到TC的SRM抑或各个OJ的月赛,我们很轻易的发现一个共同的规律——动态规划在其中稳稳的占据了一个重要的地位。可以说,掌握了动态规划,不一定会成为大牛,但是一只大牛,是肯定精通动态规划的。2009-8-12成都大学ACM暑期集训DP篇——李明金*动态规划,和分治法一样,是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分成一些独立的子问题,递归求解各子问题,然后合并子问题的解而得到原问题的解。于此不同,动态规划适用于子问题不是独立的情况,也就是各子问题包含公共的子子问题。动态规划对每个子子问题只求解一次,将其结果保存在一张表中,从而避免每次遇到各个子问题时重新计算答案。动态规划通常应用于最优化问题。此类问题可能有许多种可行解。每个解都有一个值,而我们希望找到一个具有最优(最大或最小)值的解。称这样的问题为该问题的“一个”最优解(而不是“确定的”最优解),因为可能存在多个取最优解的值。总结:自从有了动态规划,这个世界变得好美妙!2009-8-12成都大学ACM暑期集训DP篇——李明金*—状态&(状态压缩动态规划):NOJ江苏省赛回放CDE(三角形演变题)H2009-8-12成都大学ACM暑期集训DP篇——李明金*)描述最优解的结构2)递归定义最优解的值3)按自底向上的方式计算最优解的值4)由计算出的结果构造一个最优解第1-3步构成问题的动态规划解的基础。第四步只要求计算最优解的值时可以略去。如果的确做了第四步,则有时要在第三步的计算中记录一些附加信息,使构造一个最优解变得容易。2009-8-12成都大学ACM暑期集训DP篇——李明金*:装配线调度问题描述:某汽车工厂有2个装配线,每个装配线有n个装配站(按顺序编号1~n),两个装配线对应的装配站执行相同的功能,但所用的时间可能不同。经过第i条流水线(i=1,2)的第j个装配站所花的时间为Aij。从第i条流水线的第j个装配站移到第j+1个装配站的时间可以忽略,而移到另外一个流水线的下一个装配站则需要一定的时间Tij。汽车进入流水线不需要花时间,出流水线时需要花时间Tin。开始进入装配线i的时间是ei。结束离开装配线i的时间是xi。汽车的装配需要按顺序经过所有装配站。现在已知装配时间Aij和转移时间Tij,要求输出装配一辆汽车所需要的最短时间。2009-8-12成都大学ACM暑期集训DP篇——李明金*方案一:暴力搜索,穷举所有装配可能,然后选择极小。显然这个方案是不可行的,因为我们分析可知,装配方式共有2^N种(将所使用装配站一内的站看做一个集合,全集是1….N,子集就有2^N),这时时间复杂度到达O(2^N),显然N太大的时候是一定会TE的。2009-8-12成都大学ACM暑期集训DP篇——李明金*方案二:动态规划。步骤一:描述最优解的结构在这里就是通过工厂最快路线的结构其实这里就是描述问题是否具有一个最优子结构,即可以利用子问题的最优解构造原问题的一个最优解。在这道题中,观察一条通过S1,j的最快路线,我们发现,它必然是通过S1,j-1或S2,j-1中的一个的最快路线(如果不是最快,则自我矛盾,S1,j就不是最快了)为了解决这个问题,即寻找通过人一条装配线上的装配站J的最快路线,我们解决它的子问题,即寻找通过两条装配线上的装配站J-1的最快路线。所以,对于这个问题,我们可以求子问题的最优解,从而得到原问题的最优解。PS:状态,状态转移方程的概念将会在理脱出,后面会提到,只要找好了状态方程(加元等手段),就能轻松使用动态规划。2009-8-12成都大学ACM暑期集训DP篇——李明金*步骤二:一个递归的解利用子问题的最优解来递归定义一个最优解的值。在这个问题中,我们选择在两条装备线上通过装配站j的最快路线的问题作为子问题(j=1,2,3….,n)。令fi[j]表示一个底盘从起点到装配站Si,j的最快可能时间。我们的最终目标是确定底盘通过工厂的所有路线的最快时间,记做f*。f*=min(f1[n]+x1,f2[n]+x2)下面的问题就是确定f1[1]和f2[1]2009-8-12成都大学ACM暑期集训DP篇——李明金*显然,不管是从那条线路开始装配的,底盘肯定是直接到达装配站1的,也就是说之前是不用计算转移到装配站1的时间的。则