4-动态程序设计-朱全民

动态程序设计朱全民基本原理1、多阶段最优化决策：即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。带权有向的多段图上一阶段的状态下一阶段的状态决策概念⑴状态（State）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。⑵阶段（Stage）：阶段是一些性质相近，可以同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。⑶决策（Decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。⑷状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的中心。设fk(i)—k阶段状态i的最优权值，即初始状态至状态i的最优代价fk+1(i)=min{xk(j)+u(i,j)}基本原理最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。机器分配总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M=15，N=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。分析用机器数来做状态，数组F[I，J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为:F[I，J]=Max{F[I-1，K]+Value[I，J-K]}(1=I=N,1=J=M,0=K=J)初始值:F(0,0)=0时间复杂度O(N*M2)最长不下降序列设有整数序列b1,b2,b3,…,bm，若存在下标i1i2i3…in，且bi1bi2bi3…bin，则称b1,b2,b3,…,bm中有长度为n的不下降序列bi1,bi2,bi3,…,bin。求序列b1,b2,b3,…,bm中所有长度(n)最大不下降子序列输入：整数序列。输出：最大长度n和所有长度为n的序列个数。分析（1）设f(i)为前i个数中的最大不下降序列长度,则f(i)=max{f(j)+1}(1=ji=m,bjbi)边界为F(1)=1(2)设t(i)为前i个数中最长不下降序列的个数,则t(i)=∑t(j)(1=ji=m,bjbi,f(i)=f(j)-1)初始为t(i)=1当f(i)=n时，将t(i)累加举例：1234658109f:123455677t:111111222答案：f=7时，边界为∑t=4进一步(3)求本质不同的最长不下降序列个数有多少个？如：1234658109有，12346810,12345810,1234689,1234589都是本质不同的。但对于1223354f1223354t1112244答案有8个，其中4个1235，4个1234改进算法上例显然对于相两个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按b从小到大（当bi=bj时按F从大到小）排序，增设Order(i)记录新序列中的i个数在原序列中的位置。可见，求t(i)时，当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)时，便不累加t(j)。这样就避免了重复。上述算法的时间复杂度为O(n2)凸多边形三角划分给定一个具有N（N50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？输入文件：第一行顶点数N第二行N个顶点（从1到N）的权值输出格式：最小的和的值各三角形组成的方式输入示例：5122123245231输出示例：Theminimumis：12214884Theformationof3triangle:345,153,123分析设F[I,J]（IJ）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(0IKJ=N)初始条件:F[1，2]=0目标状态:F[1,N]但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算系统可靠性一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。输入文件格式：第一行：nC第二行：C1P1(0)P1(1)…P1(X1)（0=X1=[C/Ck]）…第n行：CnPn(0)Pn(1)…Pn(Xn)（0=Xn=[C/Cn]）分析例：输入：22030.60.650.70.750.80.850.950.70.750.80.80.90.95输出：0.6375设F[I,money]表示将money的资金用到前I项备用件中去的最大可靠性，则有F[I,money]=max{F[I-1,money–k*Cost[I]]*P[I,k]}(0=I=n,0=K=moneydivCost(I))初始：F[0,0]=0目标：F[n,C]快餐问题Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0=0=10)，第四行为N个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。输出:每天套餐的最大产量。分析本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。状态表示：用p[i,j,k]表示前i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。用r[i,j,k]表示第i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。态转移方程：p[i,j,k]=Max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}(0=j1=j=100,0=k1=k=100,且(j-j1)*p1+(k-k1)*p2=T[i]---第i条生产线的生产时间)r[i,j-j1,k-k1]=(T[i]-(j-j1)*p1+(k-k1)*p2)divp3;此算法的时间复杂度为O(N*1004),优化在本题中，可以在动态规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由A,B,C计算，即min｛100divA，100divB，100divc｝），接着，用贪心法计算出这N条流水线可以生产的套数，并与上限比较，大于则输出上限值并退出，否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：S1：读入数据。S2：贪心求上限并计算出一可行解，判断是否需进行下一步。S3：动态规划求解。S4：输出。其他优化方法1.存储结构：由于每一阶段状态只与上一阶段状态有关，所以我们可以只用两个100*100的数组滚动实现。但考虑到滚动是有大量的赋值，可以改进为动态数组，每次交换时只需交换指针即可，这样比原来数组间赋值要快。2.减少循环次数：在计算每一阶段状态过程中无疑要用到4重循环，我们可以这样修改每一重循环的起始值和终数，其中q1,q2为A，B上限值。原起始值改进后的起始值fori:=1tondofori:=1tondoforj:=0totot[i]divp1doforj:=0tomin(q1,tot[i]divp1)dofork:=0to(tot[i]-p1*j)divp2dofork:=0tomin(q2,(tot[i]-p1*j)divp2)doforj1:=0tojdoforj1:=max(0,j-t[i]divp1)tomin(j,tot[i-1]divp1)dofork1:=0tokdofork1:=max(0,k-(t[i]-(j-j1)*p1)divp2)tomin(k,(tot[i-1]-p1*j1)divp2)do石子合并在一园形操场四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(≤20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大输入数据:第一行为石子堆数N;第二行为每堆石子数,每两个数之间用一空格分隔.输出数据:从第1至第N行为得分最小的合并方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.示例贪心法N=5石子数分别为346542。用贪心法的合并过程如下：第一次346542得分5第二次54654得分9第三次9654得分9第四次969得分15第五次159得分24第六次24总分：62然而仔细琢磨后，发现更好的方案：第一次346542得分7第二次76542得分13第三次13542得分6第四次1356得分11第五次1311得分24第六次24总分：61显然，贪心法是错误的。动态规划用data[i,j]表示将从第i颗石子开始的接下来j颗石子合并所得的分值，max[i,j]表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：max[i,j]=max(max[i,k]+max[i+k,j–k]+data[i,k]+data[i+k,j–k])(2=k=j)max[i,1]=0同样的，我们用min[i,j]表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：min[i,j]=min(min[i,k]+min[i+k,j–k]+data[i,k]+data[i+k,j–k])(0=k=j)min[i,0]=0这样，我们完美地解决了这道题。时间复杂度也是O(n2)。积木游戏一种积木游戏，游戏者有N块编号依次为1，2，…，N的长方体积木。第I块积木通过同一顶点三条边的长度分别为ai,bi,ci（i=1,2,…,N），1从N块积木中选出若干块，并将他们摞成M（1=M=N）根柱子，编号依次为1,2,…,M，要求第k根柱子的任意一块积木的编号都必须大于第K-1根柱子任意一块积木的编号（2=K=M）。2对于每一根柱子，一定要满足下面三个条件：除最顶上的一块积木外