K-动态规划教案.doc

动态规划策略动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。第一节 动态规划的本质一、多阶段决策过程的最优化问题 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程(如图)就称为多阶段决策过程，这种问题称为多阶段决策问题。阶段1阶段2阶段n决策1决策2决策n-1 在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有动态的含义，我们称这种解决多阶段决策最优化的过程为动态规划方法。 应指出，动态规划是考察求解多阶段决策问题的一种途径、一种方法，而不是一种特殊算法。不像线性规划那样，具有一个标准的数学表达式和明确定义的一组规划。因此我们在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。例如：图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少？解法一：用搜索法对A-E可能的每一条路线进行枚举，把距离算出来，然后互相比较，找出最短者。设DisX为城市X到E的最短路线的长度；（X表示任意一个城市）MapI,J表示I，J两个城市间的距离，若MapI，J=0，则两个城市不连通。 算法描述Program li_1;Var Se:未访问的城市集合； Function Long(Who:当前访问城市):Integer;求当前访问城市与城市E的最短距离 Begin If Who=E Then Search:=0 Else Begin Min:=Maxint; For I取遍所有城市 Do If （MapWho,I0） And (I In Se) Then Begin Se:=Se-I; J:=MapWho,I+Long(I);Se:=Se+I; If JMin Then Min:=J; End; Long:=Min; End; End; Begin main Se:=除A外所有城市的集合； DisA:=Long(A); End.解法分析：这个程序的时间复杂度为O(N!)，每次除了已经访问过的城市外，其他城市都要访问，所以，这是一个“指数级”的算法。我们来观察一下这个算法。在求从B1到E的最短路径的时候，先求出从C2到E的最短路径；而在求从B2到E的最短路径的时候，又求了一遍从C2到E的最短路径。也就是说，从C2到E的最短路径我们求了两遍。同样可以发现，在求从C1、C2到E的最短路径的过程中，从D1到E的最短路径也被求了两遍。而在整个程序中，从D1到E的最短路径被求了四遍。如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，随时调用，那么算法就会简洁多了！解法二：由后往前依次推出每个Dis值，直到推出DisA为止。所谓“后”、“前”是我们自己为城市编的序号，当两个城市I，J的前后顺序定为I“前”J“后”时，必须满足这个条件：或者I，J不连通，或者DisI+MapI,JDisJ。 因为如果I，J连通且DisI+MapI,JB2-C4-D3-E 为从A到E的最短路线。最短路线长13。从上面的计算过程中，我们可以看出，在求解的各个阶段，我们利用了K阶段与K+1阶段之间的如下关系： Fk（ Uk）=minSk（Uk，Xk）+Fk+1（Xk） k=4，3，2，1，0 F5（ U5）=0这种递推关系，叫做动态规划的状态转移方程。该动态规划解法的基本思想：若以Uk表示第K阶段的一个决策点，从终点开始，依逆向求出倒数第一阶段、倒数第二阶段、倒数第三阶段、倒数第N-1阶段中各点到达终点的最短路线。最终求出从起点到终点的最短路线。这就是动态规划。动态规划的最优化概念是在一定条件下，我到一种途径，在对各阶段的效益经过按问题具体性质所确定的运算以后，使得全过程的总效益达到最优。决策过程：（1）由目标状态E向前推，可以分成3个阶段，即3个子问题。（2）策略：每个阶段到E的最省费用为本阶段的决策路径。（3）D1，D2，D3是第一次输人的结点。他们到E都只有一种费用，目前无法定下，那一个点将在全程最优策略的路径上。第二阶段计算中，都应分别参加计算。（4）C1，C2，C3，C4是第二次输入结点，他们到D1，D2，D3各有两种费用。此时应计算C1，C2，C3，C4分别到E的最少费用。（5）C1的决策路径是 min（C1D1）+（D1E），（C1D2）+(D2E)。同理C2 ，C3，C4,此时也无法定下第一，二阶段的城市那二个将在整体的最优决策路径上程序：将节点A-E顺序编号为1-11,按节点的逆序进行计算的方法program Li1;const n=11;var a:array1.n,1.n of integer; p:text; b,c:array1.n of integer;b记录到e的最短路径长，c记录路径 i,j,k,t:integer;beginassign(p,INPUT1.txt);reset(p);for i:=1 to n do begin for j:=1 to n do read(p,ai,j); readln(p); end;bn:=0; cn:=0;for k:=n-1 downto 1 do for t:=k+1 to n do if ak,t0 then 有路径 if bk=0 then begin ck:=t; bk:=bt+ak,t; end else if bkbt+at,k then begin ck:=t; bk:=bt+ak,t; end;writeln(b1);输出A-E的最短路径for i:=1 to n do write(ci:2, ); writeln;输出路径各节点for i:=1 to n do write(bi:2, ); writeln; 输出各点到E的最短路径end.输入数据：input1.txt为11个点的邻接矩阵。分析：这个程序的时间复杂为O(N2)。其核心为：从A到E共分为3个阶段，除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。各个阶段的决策不同，线路就不同。当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各阶段的影响。故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。从求解结果中，我们不仅得到由A点出发到终点E的最短路线及最短距离，而且还得到了从所有各中间点到终点的最短路线及最短距离，这对许多实际问题来讲是很有用的。二、动态规划中的主要概念和基本模型的构成1阶段和阶段变量：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。描述阶段的变量成为阶段变量，一般用k表示。2状态和状态变量：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。描述状态的变量成状态变量，一般用Uk表示第K个阶段的状态。如图1中，阶段3就有三个状态结点U3 =d1,d2,d3。3. 决策、决策变量和决策允许集合：从某阶段的一个状态演变到下一个阶段某状态的所作出某种选择性的行动就是决策。一个实际问题可能要有多次决策和多个决策点，在每一个阶段中都需要一次决策，决策可以用变量来描述，称为决策变量。一般用Xk表示第K阶段的决策变量。在实际问题中决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合，用Sk表示第K阶段的允许决策集合。例如，S3=D1，D2，D3，它表示第三阶段可有三种不同的决策。那么Xk与Sk之间的关系是Uk+1=Xk（Uk）。当第K阶段的状态确定之后，可能作出的决策范围还要受到这一状态的影响，这就是说，决策变量Xk是状态变量Uk的函数，记为Xk（Uk），简记为Xk。把Xk的取值范围记为Sk(Uk)，显然有Xk(Uk)Sk(Uk)。4策略和最优策略所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量Xk(Uk)所组成的有序总体称为策略。在实际问题中，可供选择的策略有一定的范围，该范围称为允许策略集合P。从P中找出最优效果的策略称为最优策略。5状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策变量就是后一阶段的状态变量，这种关系描述了由K阶段到K十1阶段状态的演变规律，称为状态转移方程。如上图的状态转移方程为UK+1=Xk（Uk）。6目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。动态规划的基本模型如下：（1） 确定问题的决策对象（2） 对决策过程进行划分（3） 对各阶段确定状态变量（4） 根据状态变量确定费用函数和目标函数（5） 建立个阶段状态变量的转移过程，确定状态转移方程。三、运用动态规划需符合的条件任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同理，动态规划也并不是万能的。什么样的问题可以采用动态规划算法？一般来说，必须满足最优化原理和无后效性。1 动态规划的最优化原理作为整个过程的最优策略具有这样的性质: 不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。利用这个原理，可以把多阶段决策问题的求解过程看成是一个连续的逆推过程。由后向前逐步推算。在求解时，各种状态前面的状态和决策，对后面的子问题，只不过相当于其初始条件而己，不影晌后面过程的最优策略。如图，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J是B到C的最优路径，则A到C的路线取I和J比I和J更优，这与原名题矛盾。从而证明J必是B到C的最优路径。 最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。2 动态规划的无后效性原则：某阶段的状态一旦确定，此后的过程演变不会再受此前各状态的影响。即：状态I只能由状态I+1通过状态转移方程得来，与其它状态无关。特别是与其它未发生的状态无关。四、动态规划中的子问题的重叠性前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优化原理），则可以考虑用动态规划解决。动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题，决策策略是阶段最优，但不一定全局最优。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。在本例中我们看到，动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。但从空间复杂度来看，动态规划算法为O(n2)，而搜索算法为O(n)，搜索算法反而优于动态规划算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。设原问题的规模为n，容易看出，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势了。第二节 动态规划的设计与实现一、动态规划算法的基本步骤设计一个标准的动态规划算法，通常可按以下几个步骤进行：阶段1阶段2阶段n决策1决策2决策n-11. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。 2. 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 3. 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 4. 寻找边界条件：给出的状态转移方程只是一个递推式，是一个通用形式化表达式。需要给出递推的终止条件和边界值。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。5. 根据计算最优值时得到的信息，构造一个最优解。步骤1-4是动态规划算法的基本步骤。在只需要求出最优值的情形，本步骤可以省略，若需要求出问题的一个最优解，则必须执行本步骤。此时，在步骤1-4中计算最优值时，通常需记录更多的信息，以便在本步骤中使用。6. 程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：标准动态规划的基本框架1. 对fn+1(xn+1)初始化; 边界条件2. for k:=n downto 1 do 逆推求解3. for 每一个xkXk do4. for 每一个u kU k(x k) do begin5. f k(x k):=一个极值; 或6. xk+1:=Tk (xk,uk); 状态转移方程7. t:=(fk+1(xk+1),vk(xk,uk); 8. if t比fk(xk)更优 then fk(xk):=t; 计算fk(xk)的最优值 end; 9. t:= 一个极值; 或10. for 每一个x1X1 do11. if f1(x1)比t更优 then t:=f1(x1); 求出一个最优解12. 输出t;但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：1. 分析最优解的性质，并刻划其结构特征。 2. 递归地定义最优值。 3. 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。 73 88 1 02 7 4 44 5 2 6 54. 根据计算最优值时得到的信息，构造一个最优解。 二、动态规划的经典例题1、 数字三角形问题如图所示的一个数字三角形宝塔中，数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。任务一：假设三角形行数10，键盘输入一个确定的整数值M，编程确定是否存在一条路径，使得沿着该路径所经过的数字的总和恰为M，若存在则给出所有路径，若不存在，则输出“No nswer！”字样。任务二：假设三角形行数100，编程确定一条路径，使得沿着该路径所经过的数字的总和最大，输出最大总和及经过的路径。任务一分析：由于数字三角形的行数不大（n10），很容易想到用枚举的方法去解决，即列举出所有路径并记录每一条路径所经过的数字总和，然后判断数字总和是否等于给定的整数值M。而合理地选择枚举的方法，可以优化问题的解法，由于从塔顶到底层每次都只有两种走法，即左或右。为此，不妨用“0”表示左下，用“1”表示右下，对于层数为n的数字塔，从顶到底的一种走法可用一个n1位的二进制数表示。这样就可以用一个nl位的二进制数来模拟走法和确定解的范围。穷举出从0到2n一1个十进制数所对应的n1位二进制串对应的路径中的数字总和，判定其是否等于M而求得问题的解。任务二分析：由于三角形行数100，枚举量过大不适宜采用枚举方法。但通过分析可以得出这样一个结论：如果得到一条由顶至底的最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数据之和也为最大。因此该问题是一个典型的多阶段决策的最优化问题。按三角形的行划分阶段，若行为n则问题可划分为n-1个阶段。可以采用顺推法：从顶点出发，依顺向求出第一阶段、第二阶段第n-1阶段中个决策点的最佳路径，最终求出始点到终点的最佳路径。设：Fk(Uk)为k阶段Uk点到三角形顶点的最佳路径的最大数字和。 Uk1和Uk2为k-1阶段中Uk点的左边和右边路径上的点。 D(Uk)为k阶段中Uk点上的数字。因此可以得出顺推的状态转移方程： Fk(Uk)=maxFk-1(Uk1), Fk-1(Uk2)+D(Uk) k=1n Fo(Uo)=0 经过一次顺推后，可以得出n条路径，求出其中的最大值即可。为了程序处理的方便，我们也可以采用逆推法。设：Fk(Uk)为k阶段Uk点到三角形底边的最佳路径的最大数字和。 Uk1和Uk2为k+1阶段中Uk点的左边和右边路径上的点。 D(Uk1)和D(Uk2)为k+1阶段中Uk点的左边和右边路径上点的数字。因此可以得出顺推的状态转移方程： Fk(Uk)=maxFk+1(Uk1), Fk+1(Uk2)+D(Uk) k=1n-1 Fn(Ux)= D(Ux) x=1n求得的F1(U1)即为所求。程序：顺推法program li2_shun; const nmax=10; var d,f:array1.nmax,0.nmax of integer; n,m1,m2,i,j:integer; p:text; t:array1.nmax,1.nmax of integer;procedure printline(i,j:integer);输出路径begin if i1 then if ti,j=-1 then printline(i-1,j-1) else printline(i-1,j); write(di,j, );end;beginmain writeln; fillchar(p,sizeof(p),0);fillchar(d,sizeof(d),0); assign(p,input.txt);reset(p); readln(p,n); for i:=1 to n do begin for j:=1 to i do read(p,di,j);readln(p);end;close(p); f1,0:=0;f1,1:=d1,1;t1,1:=0; for i:=2 to n do for j:=1 to i do begin m1:=fi-1,j-1;m2:=fi-1,j; if m1=m2 then begin fi,j:=m1+di,j ;ti,j:=-1;end else begin fi,j:=m2+di,j;ti,j:=0;end; end; m1:=1; for i:=2 to n do if fn,m1=fn,i then m1:=i; writeln(maxtotal=,fn,m1); printline(n,m1);end. 程序：逆推法program li2_ni; const nmax=10; var d,f:array1.nmax,1.nmax+1 of integer; n,m1,m2,i,j:integer; p:text; t:array1.nmax,1.nmax of integer;procedure printline(i,j:integer);begin write(di,j, ); if i=m2 then begin fi,j:=m1+di,j ;ti,j:=0;end else begin fi,j:=m2+di,j;ti,j:=1;end; end; writeln(maxtotal=,f1,1); printline(1,1);end.输入数据input.txt为73 88 1 02 7 4 44 5 2 6 58 5 6 3 5 7结果：maxtotal=36 7 3 8 7 5 62、0-1背包问题对容量为c 的背包进行装载。需从n 个物品中选取装入背包的物品，每件物品的重量为wi，价值为pi。求如何装入物品使得总价值最大。分析：对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即pixi 取得最大值。设knap(I,j,c)表示从I到j号物品装入容量为c的包中。我们求xi0,1(1in)，使knap(1,n,c)为最优解。定理：fk(c)表示knap(1,n,c)的最优解值，则 f0(c)=0, c=0f0(c)=-, c0对k-1决策后，决策k fk(c) :剩余容量不足以装入wk,不产生新价值 剩余容量可以装入wk,增加新价值pk。F1(c)=Maxf0(c),f0(c-w1)+p1=max0,f0(c-w1)+p1,W1c则f1(c)=0,否则f1(c)=p1程序：Program li_2;var w,p,x:array 1.100 of integer;w记录物体的重量，p记录物体的价值，x所求的解n,c,i,j: integer;procedure readp;读入数据var ff: text; st: String;i: integer;beginwrite (Fle name:);readln(st);assign(ff, st);reset(ff);readln(ff,n,c);for i:=1 to n do readln(ff,wi,pi);close (ff);end;function f(k,c:integer):integer; 动态规划求解var t0,t1: integer;begin if ct0 then begin xk:=1;f:=t1;end else begin xk:=0;f:=t0;end; end;end;beginwriteln;writeln(=);readP;writeln(max=,f(n,c);for i:=1 to n do writeln(wi:5,pi:5,xi:5);end.3、最长非降子序列给定一个由N:N=1000个正整数组成的序列，从中间删除M个数，使剩下的序列非降，求M的最小值。 分析:通过分析题意，求M的最小值，实际上是求包含在这N个数中的最长非降序列。这是一道典型的动态规划问题。假设bi表示第i到第n个数中，保留第i个数可获得的最长非降子序列的长度,这样就可以用倒推的方法，依次求出bn,bn-l,，b1,而max（bi）(1=i=bi) and (aj=ai) then bi:=bj+1;寻找中间过程输出i:=b0-1;最长非降序列的长度writeln (min m = ,n-i);输出最小的m值writeln(the longest string:);输出非降序列数据j:=1;while i0 do begin While bji do inc(j);write(aj:5);i:=i-1;end;end;begin mainwriteln;writeln(=);readP;main;end.4、生产计划问题工厂生产某种产品，每单位(千件)的成本为1(千元)，每次开工的固定成本为3(千元)，工厂每季度的最大生产能力为6(千件)。经调查，市场对该产品的需求量第一、二、三、四季度分别为 2，3，2，4(千件)。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本(少付固定成本费)，但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5(千元)。还规定年初和年末这种产品均无库存。试制订一个生产计划，即安排每个季度的产量，使一年的总费用(生产成本和存储费)最少。 分析：这是一个明显的多阶段问题，我们按照季度自然划分阶段k，状态定义为每阶段开始时的存储量xk，决策为每个阶段的产量uk，设每个阶段的需求量（已知）为dk，则状态转移方程为：设每个阶段开工固定成本费用为a，生产单位数量产品的成本为b，每阶段单位数量产品的存储费用为，阶段指标函数为阶段的生产成本费用和存储费用之和，即：指标函数Vkn为vk之和，最优值函数fk(xk)为从第k阶段的状态xk出发到过程终结(年底)的最小费用，满足其中允许决策集合Uk由每阶段的最大生产能力决定，设过程终结时允许存储量为x0n+1，则终端条件为：将以上各式代入到标准动态规划的框架中，就可以求得最优解。程序：5、石子合并在一个圆形操场的四周摆放着N堆石子(N= 100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(=20)。 (1)选择一种合并石子的方案,使得做N1次合并,得分的总和最小; (2)选择一种合并石子的方案,使得做N1次合并,得分的总和最大;输入数据: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔。输出数据: 从第一至第N行为得分最小的合并方案。第N+1行是空行。从第N+2行到第2N+2行是得分最大合并方案。每种合并方案用N行表示,其中第i行(1=i=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可)。要求将待合并的两堆石子数以*表示，以便于识别。例如：输入: 4 4 5 9 4输出:* * * * * * * *14 * *18*仔细琢磨后，发现更好的方案*3 *4 6 5 4 2*7 *6 5 4 213 5 *4 *213 *5 *6*13 *11*24总分61用贪心法的合并过程*3 4 6 5 4 *2*5 *4 6 5 49 6 *5 *4*9 *6 9*15 *9*24总分62分析：看到本题很容易想到贪心法，几每次选取相邻最大或最小的两堆合并。经过一些小的数据的测试和尝试，答案好像是正确的。然而本题是否就可以确定用贪心法求解？我们不妨看下一个例子。设N=6，且6堆石子数分别是3 4 6 5 4 2显然，贪心法是错误的，贪心法只能导致局部最优，而局部最优并不能导致全局最优。仔细观察后，我们发现此题可以采用动态规划方法解决。我们用dataI,j表示将从第I颗石子开始的接下来j颗石子合并所得的分值，maxI,j 表示将从第I颗石子开始的接下来j颗石子合并可能的最大值，那么：maxI,j=max(maxI,k+maxI+k,j-k+dataI,k+dataI+k,j-k) (2=k=j),初始值maxI,1=0;同理，我们用dataI,j表示将从第I颗石子开始的接下来j颗石子合并所得的分值，minI,j 表示将从第I颗石子开始的接下来j颗石子合并可能的最小值，那么：minI,j=min(minI,k+minI+k,j-k+dataI,k+dataI+k,j-k) （0=kpf,j then mf,j:=mf,j+1 else mf,j:=pf,j; 动态规划求解for i:=f-1 downto 1 do begin for j:=v downto 1 do if mI+1,j+10 then mi,j:=mi+1,j+1+pi,j else mI,j:=pI,j; for j:=v downto