动态规划与斐波那契数列问题

【动态规划】动态规划与斐波那契数列问题,最短路径问题1、动态规划算法动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。基本思想若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。与分治法区别动态规划算法与分治法类似，都使用了将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优值的思路，但动态规划不是分治法关键在于分解出来的各个子问题的性质不同。分治法要求各个子问题是独立的即不包含公共的子问题，因此一旦递归地求出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不必要的工作，重复地解公共的子问题。动态规划与分治法的不同之处在于动态规划允许这些子问题不独立即各子问题可包含公共的子问题，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。相关术语1阶段把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同，描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。2状态状态表示每个阶段开始面临的自然状况或客观条件，也称为不可控因素。过程的状态通常可以用一个或一组数来描述,称为状态变量。一般状态是离散的,但有时为了方便也将状态取成连续的。3无后效性状态具有下面的性质,如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路,所通过的点,的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。4决策一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择行动称为决策。在最优控制中,也称为控制。在许多间题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。5策略由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。6最优性原理作为整个过程的最优策略,它满足,相对前面决策所形成的状态而言,余下的子策略必然构成最优子策略。问题特征1最优子结构当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2重叠子问题在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。算法步骤1分析最优值的结构，刻画其结构特征；2递归地定义最优值；3按自底向上或自顶向下记忆化的方式计算最优值。2、斐波那契数列FIBONACCIPOLYNOMIAL计算斐波那契数列FIBONACCIPOLYNOMIAL的一个最基础的算法是，直接按照定义计算CPPVIEWPLAINCOPY1/3M1未优化斐波那契数列计算2INCLUDE“STDAFXH“3INCLUDE45USINGNAMESPACESTD67VOIDINPUTINT8INTFIBINTN910INTMAIN1112INTN13INPUTN14COUTN222324INTFIBINTN2526IFN0|N12728RETURN12930ELSE3132RETURNFIBN1FIBN23334以上代码在N5时，FIB5的计算过程如下1FIB52FIB4FIB33FIB3FIB2FIB2FIB14FIB2FIB1FIB1FIB0FIB1FIB0FIB15FIB1FIB0FIB1FIB1FIB0FIB1FIB0FIB1由上面可以看出，这种算法对于相似的子问题进行了重复的计算，因此不是一种高效的算法。实际上，该算法的运算时间是指数级增长的。改进的方法是，我们可以通过保存已经算出的子问题的解来避免重复计算CPPVIEWPLAINCOPY1/3M1避免重复运算的斐波那契数列运算2INCLUDE“STDAFXH“3INCLUDE4INCLUDE5USINGNAMESPACESTD67VOIDINPUTINT8INTFIBINTN,MAP910INTMAIN1112MAPMY_MAP13INTN14INPUTN15COUTN232425INTFIBINTN,MAPMY_MAP2627IFN0|N12829RETURN13031ELSE3233MAPITERATORITERMY_MAPFINDN34IFITERMY_MAPEND3536INTTEMPFIBN1,MY_MAPFIBN2,MY_MAP37MY_MAPINSERTPAIRN,TEMP38RETURNTEMP3940ELSE4142RETURNITERSECOND434445将前N个已经算出的前N个数保存在数组MAP中，这样在后面的计算中可以直接易用前面的结果，从而避免了重复计算。算法的运算时间变为ON。3、最短路径问题现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试找出从结点A到结点E的最短距离。我们可以用深度优先搜索法来解决此问题，该问题的递归式为其中是与V相邻的节点的集合，WV,U表示从V到U的边的长度。具体算法如下下CPPVIEWPLAINCOPY1/3M1未优化的图的最短路径问题2INCLUDE“STDAFXH“3INCLUDE4INCLUDE5INCLUDE6USINGNAMESPACESTD78IFSTREAMFIN“INTXT“9DEFINEMAXLENGTH201011INTMATRIXMAXLENGTHMAXLENGTH/有向图的邻接表12INTTRACEMAXLENGTH/记录下最短线路13STRINGNODEMAXLENGTH“A“,“B1“,“B2“,“C1“,“C2“,“C3“,“C4“,“D1“,“D2“,“D3“,“E“/节点标记14INTV_N/节点个数1516INTMINDISTANCEINTV1718INTMAIN1920FINV_N21FORINTI0IMATRIXIJ26COUT“36WHILEMIND03738COUT“39MINDMINDMATRIXKTRACEK40KTRACEK4142COUT05354TMATRIXVIMINDISTANCEI55IFMINTMINTJI565758TRACEVJ59RETURNMIN60这个程序的效率如何呢我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为ON，这是一个“指数级”的算法，那么，还有没有更好的算法呢首先，我们来观察一下这个算法。在求从B1到E的最短距离的时候，先求出从C2到E的最短距离；而在求从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两遍。同样可以发现，在求从C1、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同时将求得的最短距离“记录在案“，随时调用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从V到E的最短距离记录下来，在算法中递归地求MINDISTANCEV时先检查以前是否已经求过了MINDISTANCEV，如果求过了则不用重新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有N个，因此不同的状态数目有N个，该算法的数量级为ON。CPPVIEWPLAINCOPY1/3M4避免重复运算的图的最短路径问题2INCLUDE“STDAFXH“3INCLUDE4INCLUDE5INCLUDE6USINGNAMESPACESTD78IFSTREAMFIN“INTXT“9DEFINEMAXLENGTH201011INTMATRIXMAXLENGTHMAXLENGTH/有向图的邻接表12INTMINPATHMAXLENGTH/存储这每个节点到终点的最短路径13INTTRACEMAXLENGTH/记录下最短线路14STRINGNODEMAXLENGTH“A“,“B1“,“B2“,“C1“,“C2“,“C3“,“C4“,“D1“,“D2“,“D3“,“E“/节点标记15INTV_N/节点个数1617INTMINDISTANCEINTV1819INTMAIN2021FINV_N22FORINTI0IMATRIXIJ27COUT“38WHILEMIND03940COUT“41MINDMINDMATRIXKTRACEK42KTRACEK4344COUT0RETURNMINPATHV51IFVV_N1RETURN0/边界值52INTMIN1000,T,J53FORINTIV1I05657TMATRIXVIMINDISTANCEI58IFMINTMINTJI596061MINPATHVMIN62TRACEVJ63RETURNMINPATHV64运行结果程序利用数组MINPATH存储这每个节点到终点的最短路径，避免子问题的重复运算。关于最短路径问题的的算法目前有DIJKSTRA算法、A算法、BELLMANFORD算法、SPFA算法BELLMANFORD算法的改进版本、FLOYDWARSHALL算法、JOHNSON算法、BIDIRECTIONBFS算法等。由于笔者这里主要侧重介绍动态规划思想初步，以最短路径作为例子，并没有介绍这个问题的方方面面。感兴趣的读者可以在维基百科最短路问题进一步研究。【动态规划】矩阵连乘问题问题描述给定N个矩阵A1,A2,AN，其中AI与AI1是可乘的，I1，2，N1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。问题解析由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即ABC例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式A1A2A3A4，A1A2A3A4，A1A2A3A4，A1A2A3A4，A1A2A3A4。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。看下面一个例子，计算三个矩阵连乘A1，A2，A3；维数分别为10100,1005,550按此顺序计算需要的次数A1A2A310X100X510X5X507500次，按此顺序计算需要的次数A1A2A310550101005075000次所以问题是如何确定运算顺序，可以使计算量达到最小化。算法思路例设要计算矩阵连乘乘积A1A2A3A4A5A6，其中各矩阵的维数分别是A13035A23515A3155A4510A51020A62025递推关系设计算AIJ，1IJN，所需要的最少数乘次数MI,J，则原问题的最优值为M1,N。当IJ时，AIJAI，因此，MII0，I1,2,N当I6USINGNAMESPACESTD78CONSTINTL7910INTRECURMATRIXCHAININTI,INTJ,INTS,INTP/递归求最优解11VOIDTRACEBACKINTI,INTJ,INTS/构造最优解1213INTMAIN1415INTPL30,35,15,5,10,20,251617INTSNEWINTL18FORINTI0I6USINGNAMESPACESTD78CONSTINTL7910INTLOOKUPCHAININTI,INTJ,INTM,INTS,INTP11INTMEMOIZEDMATRIXCHAININTN,INTM,INTS,INTP1213VOIDTRACEBACKINTI,INTJ,INTS/构造最优解1415INTMAIN1617INTPL30,35,15,5,10,20,251819INTSNEWINTL20INTMNEWINTL21FORINTI0I04849RETURNMIJ5051IFIJ5253RETURN0545556INTULOOKUPCHAINI,I,M,S,PLOOKUPCHAINI1,J,M,S,PPI1PIPJ57SIJI58FORINTKI1K0，则表示其中存储的是所要求子问题的计算结果，直接返回即可。否则与直接递归算法一样递归计算，并将计算结果存入MIJ中返回。备忘录算法耗时ON3，将直接递归算法的计算时间从2N降至ON3。3、动态规划迭代实现用动态规划迭代方式解决此问题，可依据其递归式自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案。每个子问题只计算一次，而在后面需要时只需简单检查一下，从而避免了大量的重复计算，最终得到多项式时间的算法。CPPVIEWPLAINCOPY1/3D12矩阵连乘动态规划迭代实现2/A13035A23515A3155A4510A51020A620253/P0630,35,15,5,10,20,254INCLUDE“STDAFXH“5INCLUDE6USINGNAMESPACESTD78CONSTINTL7910INTMATRIXCHAININTN,INTM,INTS,INTP11VOIDTRACEBACKINTI,INTJ,INTS/构造最优解1213INTMAIN1415INTPL30,35,15,5,10,20,251617INTSNEWINTL18INTMNEWINTL19FORINTI0I0，XIYJ时，CIJCI1J11；当I,J0，XIYJ时，CIJMAXCIJ1,CI1J，由此建立递推关系如下构造最优解由以上分析可知，要找出XX1,X2,XM和YY1,Y2,YN的最长公共子序列,可以按一下方式递归进行当XMYN时，找出XM1和YN1的最长公共子序列，然后在尾部加上XMYN即可得X和Y的最长公共子序列。当XMYN时，必须解两个子问题，即找出XM1和Y的一个最长公共子序列及X和YN1的一个最长公共子序列。这两个公共子序列中较长者为X和Y的最长公共子序列。设数组BIJ记录CIJ的值由哪一个子问题的解得到的，从BMN开始，依其值在数组B中搜索，当BIJ1时，表示XI和YJ的最长公共子序列是由XI1和YJ1的最长公共子序列在尾部加上XI所得到的子序列。当BIJ2时，表示XI和YJ的最长公共子序列与XI1和YJ1的最长公共子序列相同。当BIJ3时，表示XI和YJ的最长公共子序列与XI和YJ1的最长公共子序列相同。代码如下CPPVIEWPLAINCOPY1/3D31最长公共子序列问题2INCLUDE“STDAFXH“3INCLUDE4USINGNAMESPACESTD56CONSTINTM77CONSTINTN689VOIDOUTPUTCHARS,INTN10VOIDLCSLENGTHINTM,INTN,CHARX,CHARY,INTC,INTB11VOIDLCSINTI,INTJ,CHARX,INTB1213INTMAIN1415/XA,B,C,B,D,A,B16/YB,D,C,A,B,A17CHARX,A,B,C,B,D,A,B18CHARY,B,D,C,A,B,A1920INTCNEWINTM121INTBNEWINTM122FORINTI0ICIJ16970CIJCI1J71BIJ27273ELSE7475CIJCIJ176BIJ3777879808182VOIDLCSINTI,INTJ,CHARX,INTB8384IFI0|J08586RETURN8788IFBIJ18990LCSI1,J1,X,B91COUT4USINGNAMESPACESTD56CONSTINTM77CONSTINTN689VOIDOUTPUTCHARS,INTN10VOIDLCSLENGTHINTM,INTN,CHARX,CHARY,INTC11VOIDLCSINTI,INTJ,CHARX,INTC1213INTMAIN1415/XA,B,C,B,D,A,B16/YB,D,C,A,B,A17CHARX,A,B,C,B,D,A,B18CHARY,B,D,C,A,B,A1920INTCNEWINTM121FORINTI0ICIJ16667CIJCI1J6869ELSE7071CIJCIJ1727374757677VOIDLCSINTI,INTJ,CHARX,INTC7879IFI0|J08081RETURN8283IFCIJCI1J118485LCSI1,J1,X,C86COUTCIJ18990LCSI1,J,X,C9192ELSE9394LCSI,J1,X,C9596运行结果如下从运行结果中可以看出，算法LCS回溯算法仅仅打印了其中一条最大公共子序列，如果存在多条公共子序列的情况下。怎么解决对BIJ二维数组的取值添加一种可能，等于4，这代表了我们说的这种多支情况，那么回溯的时候可以根据这个信息打印更多可能的选择。你从（7,6点开始按BIJ的值指示的方向回溯，把所有的路径遍历一遍，如果是能达到起点（1,1的路径，就是LCS了，有多少条打印多少条。可是，在回溯路径的时候，如果采用一般的全搜索，会进行了很多无用功。即重复了很多，且会遍历了一些无效路径，因为这些路径最终不会到达终点1,1，因此加大算法复杂度和时间消耗。博文求所有最大公共子序列的算法实现给出了一种“矩行搜索“的解决办法降低了算法的复杂度。算法主要是利用两个栈STORE,PRINT，一个用来储存节点，一个用来打印节点。栈的实现代码如下文件STACKHCPPVIEWPLAINCOPY1/2头文件HEADFILE3/45TEMPLATE6CLASSSTACKNODE7PUBLIC8TDATA9STACKNODENEXT101112TEMPLATE13CLASSSTACK14PUBLIC15STACKVOIDTOPNULL16BOOLISEMPTYVOIDCONSTRETURNTOPNULL17VOIDPUSHCONSTTDATA18BOOLPOPTDATA19BOOLPEEKTDATACONST20STACKNODEGETSTACKNODE21PRIVATE22STACKNODETOP232425TEMPLATE26STACKNODESTACKGETSTACKNODE27RETURNTOP282930TEMPLATE31VOIDSTACKPUSHCONSTTDATA32STACKNODENODENEWSTACKNODE33NODEDATADATA34NODENEXTTOP35TOPNODE363738TEMPLATE39BOOLSTACKPEEKTDATACONST40IFISEMPTYRETURNFALSE41DATATOPDATA42RETURNTRUE434445TEMPLATE46BOOLSTACKPOPTDATA47IFISEMPTYRETURNFALSE48DATATOPDATA49STACKNODENODETOP50TOPTOPNEXT51DELETENODE52RETURNTRUE53所有最长公共子序列问题LCS矩阵搜索代码如下CPPVIEWPLAINCOPY1/3D33所有最长公共子序列问题LCS矩阵搜索2INCLUDE“STDAFXH“3INCLUDE“STACKH“4INCLUDE5USINGNAMESPACESTD67TYPEDEFINTMATRIX8CONSTINTM79CONSTINTN61011TYPEDEFSTRUCT_ELEMENT1213INTLCSLEN/当前节点的LCS长度14INTROW/当前节点的行坐标15INTCOL/当前节点的列坐标16ELEMENT1718VOIDOUTPUTCHARS,INTN1920ELEMENTCREATEELEMENTINTNLEN,INTROW,INTCOL2122MATRIXGREATEMATRIXINTROW,INTCOL23VOIDDELETEMATRIXMATRIXP,INTROW2425VOIDPRINTSTACKSTACKPS,CHARSTR,INTLEN26VOIDSEARCHEMATRIXPB,INTCURPOSX,INTCURPOSY,INT2728VOIDLCSLENGTHINTM,INTN,CHARX,CHARY,MATRIXPC,MATRIXPB29VOIDLCSCHARX,MATRIXPC,MATRIXPB,INTROW,INTCOL/矩阵搜索回溯303132INTMAIN33CHARX,A,B,C,B,D,A,B34CHARY,B,D,C,A,B,A3536MATRIXBGREATEMATRIXM,N37MATRIXCGREATEMATRIXM,N3839LCSLENGTHM,N,X,Y,C,B4041COUTS,CHARSTR,INTLEN9697IFSNULL|STRNULL98RETURN99100STACKNODESNSGETSTACKNODE101102WHILESNNULL106107108COUTPCIJ1155156PCIJPCI1J157PBIJ2158159ELSEIFPCI1JSTORE,PRINT/构造两个栈STORE，PRINT179ELEMENTSTORETOP/STORE栈的栈顶节点180ELEMENTELEMENT/临时变量181ELEMENTVIRTUALNODE/虚拟节点182INTNTOPLEN/保存STORE栈顶节点的LCS长度183INTEX1,EY1,EX2,EY2/矩形搜索的两个节点的坐标184INTI,J185186VIRTUALNODECREATEELEMENTPCROWCOL1,ROW1,COL1187188STOREPUSHVIRTUALNODE/压入虚拟节点到STORE189190WHILESTOREISEMPTY191192STOREPOP193IFSTORETOPROW1|STORETOPCOL1/如果是边界节点194195PRINTPUSHSTORETOP196PRINTSTACK/打印PRINT栈里面除虚拟节点之外的所有节点197STOREPEEK198NTOPLENELEMENTLCSLEN/当前STORE的栈顶节点的LCS长度199200/弹出PRINT栈中所有LCS长度小于等于NTOPLEN的节点/201WHILEPRINTPEEK78STRINGGETLCSLENGTHSTRING910INTMAIN1112STRINGS,T13COUTS15COUTT17COUTLEN6061LENNUMIJLENGTH62LCSNUMIJ6364ELSEIFNUMIJLENGTHLEN6566LCSLCS“,“NUMIJ676869707172FORINTI0I,即需要预处理时间复杂度为OPQ,每次查询最长公共前缀的时间复杂度为O1。遍历所有最长公共前缀的时间复杂度为OPQ,因此使用广义后缀数组解决最长公共子串的时间复杂度为OPQ。对于字符串S,T,它的广义后缀数组在不降低性能同时需要使用2PQ空间。解决2个长度分别为P,Q的字符串最长公共子串问题的动态规划算法,广义后缀树算法以及广义后缀数组算法在时间复杂度,空间复杂度以及编程实现上的比较分析总结如下表所示其中动态规划算法以及广义后缀树算法的研究已经非常成熟,在计算机算法领域有着各种各样的应用,但在解决字符串最长公共子串问题上还有一定不足,即动态规划算法占用的时间复杂度以及空间复杂度都很高,而广义后缀树算法虽然降低了时间复杂度,但其空间复杂度还是较高,另外编程实现也较难。虽然广义后缀数组的理论研究还在发展中,但就目前的研究成果而言,在解决字符串最长公共子串问题上,根据上面给出的算法,它可以综合动态规划算法以及广义后缀树算法的优点,既保证了线性的时间复杂度,较低的空间复杂度又易于编程实现。改进的后缀数组算法及相关定义应用可查看博文最长公共子串问题的后缀数组解法。【动态规划】最大子段和问题，最大子矩阵和问题，最大M子段和问题1、最大子段和问题问题定义对于给定序列A1,A2,A3AN,寻找它的某个连续子段，使得其和最大。如2,11,4,13,5,2最大子段是11,4,13其和为20。1枚举法求解枚举法思路如下以A0开始A0,A0,A1,A0,A1,A2A0,A1,AN共N个以A1开始A1,A1,A2,A1,A2,A3A1,A2,AN共N1个以AN开始AN共1个一共N1N/2个连续子段，使用枚举，那么应该可以得到以下算法具体代码如下CPPVIEWPLAINCOPY1/3D41最大子段和问题的简单算法2INCLUDE“STDAFXH“3INCLUDE4USINGNAMESPACESTD56INTMAXSUMINTN,INTA,INT78INTMAIN910INTA2,11,4,13,5,21112FORINTI0ISUM/求最大子段和3940SUMTHISSUM41BESTII42BESTJJ43444546RETURNSUM47从这个算法的三个FOR循环可以看出，它所需要的计算时间是ON3。事实上，如果注意到，则可将算法中的最后一个FOR循环省去，避免重复计算，从而使算法得以改进。改进后的代码如下CPPVIEWPLAINCOPY1/3D42最大子段和问题的避免重复的简单算法2INCLUDE“STDAFXH“3INCLUDE4USINGNAMESPACESTD56INTMAXSUMINTN,INTA,INT78INTMAIN910INTA2,11,4,13,5,21112FORINTI0ISUM3536SUMTHISSUM37BESTII38BESTJJ3940414243RETURNSUM442分治法求解分治法思路如下将序列A1N分成长度相等的两段A1N/2和AN/21N,分别求出这两段的最大字段和，则A1N的最大子段和有三中情形1、A1N的最大子段和与A1N/2的最大子段和相同；2、A1N的最大子段和与AN/21N的最大子段和相同；3、A1N的最大字段和为，且14USINGNAMESPACESTD56INTMAXSUBSUMINTA,INTLEFT,INTRIGHT7INTMAXSUMINTN,INTA89INTMAIN1011INTA2,11,4,13,5,21213FORINTI0I0ALEFT03031ELSE3233INTCENTERLEFTRIGHT/234INTLEFTSUMMAXSUBSUMA,LEFT,CENTER35INTRIGHTSUMMAXSUBSUMA,CENTER1,RIGHT3637INTS1038INTLEFTS039FORINTICENTERILEFTI4041LEFTSAI42IFLEFTSS14344S1LEFTS45464748INTS2049INTRIGHTS050FORINTICENTER1IS25455S2RIGHTS565758SUMS1S259IFSUM0时，BJBJ1AJ，否则BJAJ。由此可得BJ的动态规划递推式如下BJMAXBJ1AJ,AJ,14USINGNAMESPACESTD56INTMAXSUMINTN,INTA78INTMAIN910INTA2,11,4,13,5,21112FORINTI0I02930BAI3132ELSE3334BAI3536IFBSUM3738SUMB394041RETURNSUM42上述算法的时间复杂度和空间复杂度均为ON。2、最大子矩阵和问题1问题描述给定一个M行N列的整数矩阵A，试求A的一个子矩阵，时期各元素之和为最大。2问题分析用二维数组A1M1N表示给定的M行N列的整数矩阵。子数组AI1I2J1J2表示左上角和右下角行列坐标分别为I1,J1和I2,J2的子矩阵，其各元素之和记为最大子矩阵问题的最优值为。如果用直接枚举的方法解最大子矩阵和问题，需要OM2N2时间。注意到，式中，设，则容易看出，这正是一维情形的最大子段和问题。因此，借助最大子段和问题的动态规划算法MAXSUM，可设计出最大子矩阵和动态规划算法如下CPPVIEWPLAINCOPY1/3D45最大子矩阵之和问题2INCLUDE“STDAFXH“3INCLUDE4USINGNAMESPACESTD56CONSTINTM47CONSTINTN389INTMAXSUMINTN,INTA10INTMAXSUM2INTM,INTN,INTAMN1112INTMAIN1314INTAN4,2,9,1,3,8,6,7,6,0,9,51516FORINTI0ISUM4950SUMMAX5152535455RETURNSUM565758INTMAXSUMINTN,INTA5960INTSUM0,B061FORINTI1I06465BAI6667ELSE6869BAI7071IFBSUM7273SUMB747576RETURNSUM77以上代码MAXSUM2方法的执行过程可用下图表示3、最大M子段和问题1问题描述给定由N个整数可能为负数组成的序列A1,A2,A3AN,以及一个正整数M,要求确定此序列的M个不相交子段的总和达到最大。最大子段和问题是最大M字段和问题当M1时的特殊情形。2问题分析设BI,J表示数组A的前J项中I个子段和的最大值，且第I个子段含AJ14USINGNAMESPACESTD56INTMAXSUMINTM,INTN,INTA78INTMAIN910INTA0,2,3,7,6,4,5/数组脚标从1开始11FORINTI1II4849BIJBIJ1AJ/代表AJ同AJ1一起，都在最后一子段中50FORINTKI1K4USINGNAMESPACESTD56INTMAXSUMINTM,INTN,INTA78INTMAIN910INTA0,2,3,7,6,4,5/数组脚标从1开始11FORINTI1ICJ1BJ1AJCJ1AJ40CJ1MAX/预先保存第J1行的最大J1子段和4142IFMAX4USINGNAMESPACESTD56CONSTINTN7/凸多边形边数17INTWEIGHTN0,2,2,3,1,4,2,0,1,5,2,3,2,1,0,2,1,4,3,5,2,0,6,2,1,2,1,6,0,1,4,3,4,2,1,0/凸多边形的权89INTMINWEIGHTTRIANGULATIONINTN,INTT,INTS10VOIDTRACEBACKINTI,INTJ,INTS/构造最优解11INTWEIGHTINTA,INTB,INTC/权函数1213INTMAIN1415INTSNEWINTN16INTTNEWINTN17FORINTI0IN时，顶点IS实际编号为ISMODN。按上述递推式计算出的MI,N,1记为游戏首次删除第I条边后得到的最大得分。算法具体代码如下CPPVIEWPLAINCOPY1/3D6多边形游戏2INCLUDE“STDAFXH“3INCLUDE4USINGNAMESPACESTD56DEFINENMAX1007INTN,MNMAX1NMAX12,VNMAX18CHAROPNMAX1910VOIDMINMAXINTN,INTI,INTS,INTJ,INT11INTPLOYMAXINTN,INT1213INTMAIN1415INTP16COUTN18FORINTI1IVI22MI10VI23MI11VI24COUTOPI2627COUTERMINFER55IFMAXFMINFMIJ0MINF71IFMIJ14USINGNAMESPACESTD56CONSTINTN778INTLENGTHINTI9VOIDCOMPRESSINTN,INTP,INTS,INTL,INTB10VOIDTRACEBACEINTN,INT11VOIDOUTPUTINTS,INTL,INTB,INTN1213INTMAIN1415INTP0,10,12,15,255,1,2/图像灰度数组下标从1开始计数16INTSN,LN,BN1718COUTSIJJBMAX5051SISIJJBMAX52LIJ535455SIHEADER56575859INTLENGTHINTI6061INTK162II/263WHILEI06465K66II/26768RETURNK697071VOIDTRACEBACKINTN,INT75TRACEBACKNLN,I,S,L76SINLN/重新为S数组赋值，用来存储分段位置777879VOIDOUTPUTINTS,INTL,INTB,INTN8081/在输出SN存储位数后，S数组则被重新赋值，用来存储分段的位置82COUTJ（I）8，7，4，2，5，1，9，3，10，6在制作电路板时，要求将这N条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集NETSI，I，1IN的最大不相交子集。2、最优子结构性质记NI,JT|T,TNETS,TI,TJNI,J的最大不相交子集为MNSI,JSIZEI,J|MNSI,J|。1当I1时2当I1时J4USINGNAMESPACESTD56CONSTINTN1078VOIDMNSINTC,INTN,INTSIZE9VOIDTRACEBACKINTC,INTSIZE,INTN,INTNET,INT1011INTMAIN1213INTC0,8,7,4,2,5,1,9,3,10,6/下标从1开始14INTSIZENEWINTN11516FORINTI0I0I3031COUTCI时，考虑I，CI是否属于MNSI,J的两种情况58SIZEIJMAXSIZEI1J,SIZEI1CI11596061SIZENNMAXSIZEN1N,SIZEN1CN11626364VOIDTRACEBACKINTC,INTSIZE,INTN,INTNET,INT67M068FORINTINI1I6970IFSIZEIJSIZEI1J/此时，（I,CI是最大不相交子集的一条边7172NETMI73JCI1/更新扩展连线柱区间747576IFJC1/处理I1的情形7778NETM17980算法MNS时间和空间复杂度为ON2。TRACEBACK时间复杂度为ON。程序运行结果如下【动态规划】流水作业调度问题与JOHNSON法则1、问题描述N个作业1，2，N要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业I所需的时间分别为AI和BI。流水作业调度问题要求确定这N个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。2、问题分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N1，2，N。S是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间T后才可利用。将这种情况下完成S中作业所需的最短时间记为TS,T。流水作业调度问题的最优值为TN,0。设是所给N个流水作业的一个最优调度，它所需的加工时间为A1T。其中T是在机器M2的等待时间为B1时，安排作业2，N所需的时间。记SN1，则有TTS,B1。证明事实上，由T的定义知TTS,B1。若TTS,B1，设是作业集S在机器M2的等待时间为B1情况下的一个最优调度。则1，2，N是N的一个调度，且该调度所需的时间为A1TS,B1BI2将N1中作业按AI的非减序排序；将N2中作业按BI的非增序排序；3N1中作业接N2中作业构成满足JOHNSON法则的最优调度。JOHNSON算法中分类及排序的作用（验证不等式）设数组C为排序后的作业排列，排序结果如下红线左侧满足ACIMINBCI1,ACI其调度顺序最优；红线右侧满足BCIBCI1符合JOHNSON不等式，MINBCI,ACI1MINBCI1,ACI其调度顺序最优；中间过渡部分横向比较，左侧ACIMINBCI1,ACI其调度顺序也最优；程序具体代码如下CPPVIEWPLAINCOPY/3D9动态规划流水作业调度问题INCLUDEUSINGNAMESPACESTDCONSTINTN5CLASSJOBTYPEPUBLICINTOPERATORBIBIAI/按JOHNSON法则分别取对应的BI或AI值作为关键字DIJOBAIIJ/如果前一个数大于后一个数，则交换IFDJ0,WI0,VI0,1IN要求找一N元向量X1,X2,XN,XI0,1,WIXIC,且VIXI达最大即一个特殊的整数规划问题。2、最优性原理设Y1,Y2,YN是341的一个最优解则Y2,YN是下面相应子问题的一个最优解证明使用反证法。若不然,设Z2,Z3,ZN是上述子问题的一个最优解,而Y2,Y3,YN不是它的最优解。显然有VIZIVIYII2,N且W1Y1WIZIVIYI,I1,N说明Y1,Z2,Z3,ZN是34101背包问题的一个更优解,导出Y1,Y2,YN不是背包问题的最优解,矛盾。3、递推关系设所给01背包问题的子问题的最优值为MI，J，即MI，J是背包容量为J，可选择物品为I，I1，N时01背包问题的最优值。由01背包问题的最优子结构性质，可以建立计算MI，J的递归式注343式此时背包容量为J，可选择物品为I。此时在对XI作出决策之后,问题处于两种状态之一1背包剩余容量是J,没产生任何效益；2剩余容量JWI,效益值增长了VI；算法具体代码如下CPPVIEWPLAINCOPY1/3D101动态规划背包问题2INCLUDE“STDAFXH“3INCLUDE4USINGNAMESPACESTD56CONSTINTN478VOIDKNAPSACKINTV,INTW,INTC,INTN,INTM109VOIDTRACEBACKINTM10,INTW,INTC,INTN,INTX1011INTMAIN1213INTC814INTV0,2,1,4,3,W0,1,4,2,3/下标从1开始15INTXN116INTM10101718COUT1I6465JMAXMINWI1,C66FORINTJ0JC7273MIJMAXMI1J,MI1JWIVI/效益值增长VI747576M1CM2C77IFCW17879M1CMAXM1C,M2CW1V180818283/X数组存储对应物品01向量,0不装入背包，1表示装入背包84VOIDTRACEBACKINTM10,INTW,INTC,INTN,INTX8586FORINTI1I2N时，算法需要N2N计算时间。4、算法的改进由MI,J的递归式容易证明，在一般情况下，对每一个确定的I1IN，函数MI,J是关于变量J的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数MI,J由其全部跳跃点唯一确定。如图所示。对每一个确定的I1IN，用一个表PI存储函数MI，J的全部跳跃点。表PI可依计算MI，J的递归式递归地由表PI1计算，初始时PN10，0。一个例子N3，C6，W4，3，2，V5，2，1。函数MI,J是由函数MI1,J与函数MI1,JWIVI作MAX运算得到的。因此，函数MI,J的全部跳跃点包含于函数MI1，J的跳跃点集PI1与函数MI1，JWIVI的跳跃点集QI1的并集中。易知，S,TQI1当且仅当WIA且D4USINGNAMESPACESTD56CONSTINTN478TEMPLATE9INTKNAPSACKINTN,TYPEC,TYPEV,TYPEW,INTP,INTX10TEMPLATE11VOIDTRACEBACKINTN,TYPEW,TYPEV,TYPEP,INTHEAD,INTX1213INTMAIN1415INTC816INTV0,2,1,4,3,W0,1,4,2,3/下标从1开始17INTXN1181