《动态程序设计.ppt》由会员分享，可在线阅读，更多相关《动态程序设计.ppt（81页珍藏版）》请在课桌文档上搜索。
1、动态程序设计,基本原理,1、多阶段最优化决策：即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。,带权有向的多段图,上一阶段的状态,下一阶段的状态,决策,概念,状态（State）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。阶段（Stage）：阶段是一些性质相近，可以同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。决策（Decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。状态转移方程：是前一个阶段的状态转移到后一个的状态的演
2、变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的中心。设 fk(i)k阶段状态i的最优权值，即初始状态至状态i的最优代价 fk+1(i)=minxk(j)+u(i,j),基本原理,最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。,机器分配,总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，
3、可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M=15，N=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。,分析,用机器数来做状态，数组FI，J表示前I个公司分配J台机器的最大盈利。则状态转移方程为:FI，J=MaxFI-1，K+ValueI，J-K(1=I=N,1=J=M,0=K=J)初始值:F(0,0)=0时间复杂度O(N*M2),最长不下降序列,设有整数序列b1,b2,b3
4、,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)=maxf(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)累加举例：1 2 3 4 6 5
5、 8 10 9 f:1 2 3 4 5 5 6 7 7 t:1 1 1 1 1 1 2 2 2答案：f=7时，边界为t=4,进一步,(3)求本质不同的最长不下降序列个数有多少个？如：1 2 3 4 6 5 8 10 9 有，1 2 3 4 6 8 10,1 2 3 4 5 8 10,1 2 3 4 6 8 9,1 2 3 4 5 8 9 都是本质不同的。但对于 1 2 2 3 3 5 4 f 1 2 2 3 3 5 4 t 1 1 1 2 2 4 4 答案有8个，其中4个1 2 3 5，4个1 2 3 4,改进算法,上例显然对于相两个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按b
6、从小到大（当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）的权值输出格式：最小的和的值 各三角形组成的方式输入示例：5122 123
7、245 231 输出示例：The minimum is：12214884 The formation of 3 triangle:3 4 5,1 5 3,1 2 3,分析,设FI,J（IJ）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：FI,J=MinFI,K+FK,J+SI*SJ*SK(0IKJ=N)初始条件:F1，2=0目标状态:F1,N但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算,系统可靠性,一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备
8、用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。输入文件格式：第一行：n C第二行：C1 P1(0)P1(1)P1(X1)（0=X1=C/Ck）第 n 行：Cn Pn(0)Pn(1)Pn(Xn)（0=Xn=C/Cn）,分析,例：输入：2 20 3 0.6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.8 0.9 0.95 输出：0.6375
9、设FI,money表示将money的资金用到前I项备用件中去的最大可靠性，则有 FI,money=maxFI-1,moneyk*CostI*PI,k(0=I=n,0=K=money div Cost(I)初始：F0,0=0目标：Fn,C,快餐问题,Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道
10、如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0=0=10)，第四行为N个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。输出:每天套餐的最大产量。,分析,本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。状
11、态表示：用pi,j,k表示前i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。用ri,j,k表示第i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。态转移方程：pi,j,k=Maxpi-1,j1,k1+ri,j-j1,k-k1(0=j1=j=100,0=k1=k=100,且(j-j1)*p1+(k-k1)*p2=Ti-第i条生产线的生产时间)ri,j-j1,k-k1=(Ti-(j-j1)*p1+(k-k1)*p2)div p3;此算法的时间复杂度为O(N*1004),优化,在本题中，可以在动态规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由A,B,C计
12、算，即min100 div A，100 div B，100 div c），接着，用贪心法计算出这N条流水线可以生产的套数，并与上限比较，大于则输出上限值并退出，否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：S1：读入数据。S2：贪心求上限并计算出一可行解，判断是否需进行下一步。S3：动态规划求解。S4：输出。,其他优化方法,1.存储结构：由于每一阶段状态只与上一阶段状态有关，所以我们可以只用两个100*100的数组滚动实现。但考虑到滚动是有大量的赋值，可以改进为动态数组，每次交换时只需交换
13、指针即可，这样比原来数组间赋值要快。2.减少循环次数：在计算每一阶段状态过程中无疑要用到4重循环，我们可以这样修改每一重循环的起始值和终数，其中q1,q2为A，B上限值。原起始值 改进后的起始值for i:=1 to n do for i:=1 to n do for j:=0 to toti div p1 do for j:=0 to min(q1,toti div p1)dofor k:=0 to(toti-p1*j)div p2 do for k:=0 to min(q2,(toti-p1*j)div p2)dofor j1:=0 to j do for j1:=max(0,j-ti d
14、iv p1)to min(j,toti-1 div p1)do for k1:=0 to k do for k1:=max(0,k-(ti-(j-j1)*p1)div p2)to min(k,(toti-1-p1*j1)div p2)do,石子合并,在一园形操场四周摆放N堆石子(N100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大输入数据:第一行为石子堆
15、数N;第二行为每堆石子数,每两个数之间用一空格分隔.输出数据:从第1至第N行为得分最小的合并方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.,示例,贪心法,动态规划,用datai,j表示将从第i颗石子开始的接下来j颗石子合并所得的分值，maxi,j表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：maxi,j=max(maxi,k+maxi+k,j k+datai,k+datai+k,jk)(2=k=j)maxi,1=0同样的，我们用mini,j表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：mini,j=min(mini,k+min
16、i+k,j k+datai,k+datai+k,j k)(0=k=j)mini,0=0这样，我们完美地解决了这道题。时间复杂度也是O(n2)。,积木游戏,一种积木游戏，游戏者有N块编号依次为1，2，N的长方体积木。第I块积木通过同一顶点三条边的长度分别为ai,bi,ci（i=1,2,N），1 从N块积木中选出若干块，并将他们摞成M（1=n），x,y是上面一块积木接触面的两条边（x=y），则一定满足m.=x和n=y；下面的积木的编号要小于上面的积木的编号。请你编一程序，寻找一种游戏方案，使得所有能摞成的M根柱子的高度之和最大。,积木游戏,输入数据：文件的第一行是两个正整数N和M（1=M=N=10
17、0）,分别表示积木总数和要求摞成的柱子数。这两个数之间用一个空格符隔开。接下来的N行是编号从1到N个积木的尺寸，每行有三个1至500之间的整数，分别表示该积木三条边的长度。同一行相邻两个数之间用一个空格符隔开。输出数据：文件只有一行，是一个整数，表示所求得的游戏方案中M根柱子的高度之和,分析,设（1）fi,j,k表示以第i块积木的第k面为第j根柱子的顶面的最优方案的高度总和；（2）blocki,k 记录每个积木的三条边信息（blocki,4:=blocki,1;blocki,5:=blocki,2）。其中blocki,j+2表示当把第i块积木的第j面朝上时所对应的高，即所增加的高度；（3）ca
18、ni,k,p,kc表示第I块积木以其第k面朝上，第p块积木以第kc面朝上时，能否将积木I放在积木p的上面。1表示能，0表示不能。对于fi,j,k,有两种可能：1.除去第I块积木，第j根柱子的最上面的积木为编号为p的，若第p块积木以第kc面朝上，必须保证当第I块积木以k面朝上时能够被放在上面，即cani,k,p,kc=1；2.第i块积木是第j根柱子的第一块积木，第j-1根柱子的最上面为第p块积木，则此时第p块积木可以以任意一面朝上。则有：,动态规划,边界条件：f1,1,1:=block1,1,3;f1,1,2:=block1,1,4;f1,1,3:=block1,1,5;fi,0,k:=0;(1
19、=i=n,1=k=3);时间复杂度为O(n2*m),免费馅饼,SERKOI最新推出了一种叫做“免费馅饼”的游戏。游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。写一个程
20、序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。,免费馅饼,输入数据：输入文件的第一行是用空格分开的两个正整数，分别给出了舞台的宽度W（199之间的奇数）和高度H（1 100之间的整数）。接下来依馅饼的初始下落时间顺序给出了一块馅饼信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0 1000秒），水平位置、下落速度（1 100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。输出数据：输出文件的第一行给出了一个正整数，表示你的程序所收集到的最大分数之和。,分析,我们将问题中的馅饼信息用一个表格存储。表格的第I行第J列表示的是游戏者在第I秒到达第J列所能取
21、得的分值。那么问题便变成了一个类似数字三角形的问题：从表格的第一行开始往下走，每次只能向左或右移动一格或两格，或不移动走到下一行。怎样走才能得到最大的分值。因此，我们很容易想到用动态规划求解。FI,J表示游戏进行到第I秒，这时游戏者站在第J列时所能得到的最大分值。那么动态转移方程为：FI,J=Max FI-1,K+馅饼的分值(J-2=K=J+2),商店购物,某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不
22、是6而是5 ICU;2个花瓶加1朵花是10 ICU不是12 ICU。编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为:1朵花加2个花瓶:优惠价:10 ICU 2朵花 正常价:4 ICU,商店购物,输入数据 第一个文件INPUTTXT的格式为:第一行是一个数字B（0B5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。C 代表商品的编码（每种商品有一个
23、唯一的编码），1C999。K代表该种商品购买总数，1K5。P 是该种商品的正常单价（每件商品的价格），1P999。请注意，购物筐中最多可放5*525件商品。第二个文件OFFERTXT的格式为:第一行是一个数字S（0S99），表示共有S种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1C9 99。K代表该种商品在此组合中的数量，1K5。本行最后一个数字P（1 P9999）代表此商品组合的优惠价。当然，优惠价要低于该组合中商品正常价之总和。输出数据 在输出文件OUTPUTTXT中写 一个数字（占一行），该数字表示顾客所购商品（输入文
24、件指明所购商品）应付的最低货款。,分析,由于动态规划要满足无后效性和最优化原理，所以我们来分析此题是否满足以上两点。首先确定状态，商品不超过5种，而每种采购的数量又不超过5，那么用一个五元组来表示第i种商品买Ai的最小费用。F（A1，A2，A3，A4，A5）（1）考虑这个状态的由来，当然，我们不用优惠商品也可以买，显然这样不是最优。于是如果我们能够使用第i条商品组合的话，状态就b变为了：F（A1-SI1，A2-SI2，A3-SI3，A4-SI4，A5-SI5）（2）这样的话，状态1的费用为状态2的费用加上Si的费用，而状态2的费用必须最低（很显然，用反证法即可），同时，我们也不管状态2是如何来
25、的（因为每一个优惠商品组合的使用是没有限制的），所以本题既满足无后效性，又符合最优化原理，同时还有大量重叠子问题产生，动态规划解决此题是最好不过了。,状态转移方程,F a,b,c,d,e=MinFa-Si1,b-Si2,c-Si3,d-Si4,e-Si5+SaleCostSi(0=i=S,0=a,b,c,d,e=5)初始条件为：F a,b,c,d,e=Cost1*a+Cost2*b+Cost3*c+Cost4*d+Cost5*e,添括号问题,有一个由数字1，2，.，9组成的数字串（长度不超过200），问如何将M(M=20)个加号(+)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程
26、序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。输入格式从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），的值在输入文件的第二行行首。输出格式在屏幕上输出所求得的最小和的精确值。,分析,考虑到数据的规模超过了长整型,我们注意在解题过程中采用高精度算法.规划方程:FI,J=MIN FI-1,K+NUMK+1,J(I-1=K=J-1)边界值:F0,I:=NUM1,I;FI，J表示前J个数字中添上I个加号后得到
27、的最小值。NUMI，J表示数字串第I位到第J位的数上述问题的每一步，都只与上一步有关。因此可以采用滚动数组程序的时间效率约为 20*200*200,最长前缀,一些生物体的复杂结构可以用其基元的序列表示，而一个基元用一个大写英文字符串表示。生物学家的一个问题就是一个这样的长序列分解为基元（字符串）的序列。对于给定的基元集合P，如果可以从中选出N个基元P1，P2，P3，.,Pn，将它们各自对应的字符串依次连接后得到一个字符串S，称S可以由基元集合P构成。在从P中挑选基元时，一个基元可以使用多次，也可不用。例如，序列 ABABACABAAB 可以由基元集合A，AB，BA，CA，BBC 构成。字符串的
28、前K个字符为该字符串的前缀，其长度为K。请写一个程序，对于输入的基元集合P和字符串T，求出一个可以由基元集合P构成的字符串T的前缀，要求该前缀的长度尽可能长，输出其长度。,最长前缀,输入数据：有两个输入文件 INPUT.TXT，DATA.TXTINPUT.TXT 的第一行是基元集合P中的基元数目N（1=N=100）,随后有2N行，每两行描述一个基元，第一行为该基元的长度L（1=L=20）。随后一行是一个长度为L的大写英文字符串，表示该基元。每个基元互不相同。DATA.TXT 描述要处理的字符串T，每一行行首有一个大写字母，最后一行是一个字符.,表示字符串结束。T的长度最小为1，最大不超过500
29、000。输出数据：OUTPUT.TXT。只有一行，一个数字，表示可以由P构成的T的最长前缀的长度。,分析,本题可以简述为:从一个集合里选出若干个基元,使其组成字符串T的前缀,求最长前缀的长度.对于T的每个字符，其状态可分为两种：在此之前的所有字符（包括本身）可匹配(true)、不可匹配(false)。(可匹配是指可以由集合里的基元组成)用Fi表示第i个字符的状态，finda,b表示由第a至b位的字符组成的子串是否存在于集合中，则，Fi=Fi or(Fk and findk+1,j)(0=k=i-1)初始条件:if i=0 then Fi:=true else Fi:=false,分析,由于T的
30、长度最大达500000，无法存放所有状态，但集合里基元长度不超过20，因此可只保留当前20位字符与状态。当20位字符都不可以匹配时，停止运算，最后一个状态为true的字符的位置，即为所求。为了便于操作，可用字符串表示状态，0表false、1表true.为了便于查找，可将基元按长度存储。形如：si,j，表示长度为 i的第 j个基元。亦可采用树的结构存储基元，构造一种多叉树（最多26叉），查找时顺着相应字母，定位到相应分支。这样速度要快些，但程序更复杂。大家可以比较一下。按树结构算，时间复杂度为O(500000*L*L),勉强可以承受。,多边形,多角形是一个单人玩的游戏，开始时有一个N个顶点的多边
31、形。如图，这里N=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到N。第一步，一条边被拿走；随后各步包括如下：选择一条边E和连接着E的两个顶点V1和 V2；得到一个新的顶点，标记为V1与V2通过边E上的运算符运算的结果。最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。,样例,写一个程序，对于给定一个多边形，计算出可能的最高得分，并且列出得到这个分数的过程。,分析,分析,我们在这条“线”当中继续删边，并且每次删边都使被删边两旁的点按边上的操作符合并，图五。这样进行了n-1次删边操作后，“线”变成了一个点。我们的目的，就是安排删边的顺序，使最后的点上的数尽可能的大。
32、拿到题目之后，我们马上可以想到用枚举法枚举删边的先后顺序。但边数最大可以达到50，枚举的复杂将会有50！。因此枚举算法马上被排除了。对最优化问题的求解，我们往往可以使用动态规划来解决。这道题是不是可以使用动态规划呢？我们先对题目进行一些变化原题中顶点上的数可以为负数，现在我们规定这个数一定大于等于0；原题中边可以为乘号，现在我们规定只能为加号。题意改变后，我们想到了什么？对！“石子合并”。,动态规划,我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值 用f(I,j)表示从j开始，进行i次删边操作所能得到的最大值，num(i)表示第i个顶点上的数，那么：,进一步分析,现在我们来考虑加
33、入乘号后的情况。由于所有的顶点上的数都为非负数，因此即使有了乘法，函数f的无后效性并不被破坏。我们可以在前一方程的基础上进行改进：（opr(i)表示第i条边上的操作符）,进一步分析,最后，我们允许顶点上出现负数。以前的方程还适不适用呢？这个例子的最优解应该是（3+2）*（-9）*（-5）=250，然而如果沿用以前的方程，得出的解将是（-10）*3+2）*（-5）=140。为什么？我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。,最终？,我们引入函数fmin和fmax来解决这个问题。fmax(I,j)表示从
34、j开始，进行i次删边操作所能得到的最大值，fmin(I,j)表示从j开始，进行i次删边操作所能得到的最小值。,函数actmax与actmin的构造是十分关键的。首先讨论actmax(x1,y1,x2,y2)的构造：当opr(x2-1)=+时，actmax=fmax(x1,y1)+fmax(x2,y2)当opr(x2-1)=*时，actmax=max(fmax(x1,y1)*fmax(x2,y2),fmin(x1,y1)*fmin(x2,y2),完美解决,接下来讨论actmin(x1,y1,x2,y2)的构造：当opr(x2-1)=+时，actmin=fmin(x1,y1)+fmin(x2,y2
35、)opr(x2-1)=*时，actmin=min(fmax(x1,y1)*fmin(x2,y2),fmin(x1,y1)*fmax(x2,y2)到此为止，整个问题圆满解决了。算法的空间复杂度为n2，算法时间复杂度为n4（先要枚举每一条边，然后再用复杂度为n3的动态规划解决）。,选课,大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，数据结构必须在选修了高级语言程序设计之后才能选修
36、。我们称高级语言程序设计是数据结构的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，。,选课,下面举例说明上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。,选课,输入 输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1M1
37、000)，N表示学生可以选的课程总数（1NM)。以下M行每行代表一门课，课号依次为1，2M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。输出 输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。,样例分析,分析,们可以选取某一个点k的条件只是它的父节点已经被选取或者它自己为根节点；而且我们不论如(何取k的子孙节点，都不会影响到它父节点的选取情况，这满足无后效性原则。于是我们猜测，是不是可以以节点为阶段，进行动态规划呢？我们用函数f(I,j)表示以第i个
38、节点为父节点，取j个子节点的最佳代价，则：可是如此规划，其效率与搜索毫无差别，虽然我们可以再次用动态规划来使它的复杂度变为平方级，但显得过于麻烦。,改造树,转变为二叉树。如果两节点a,b同为兄弟，则将b设为a的右节点；如果节点b是节点a的儿子，则将节点b设为节点a的左节点。树改造完成后如图3。我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，这和前一个函数表示的意义是一致的，但方程有了很大的改变：,动态规划,1=i=m,1=j=n,0=kj 这个方程的时间复杂度最大为n3，十分优秀了。在具体实现这道题时，我们可以自顶而下，用递归进行树的遍历求解,HPC(Winter Ca
39、mp 2001),描述抽象为：A类任务：A1，A2，AmB类任务：B1，B2，BnP个接点：1，2，P在节点i连续处理x个A、B类任务的时间 Kia x2、Kib x2节点i转入工作状态A、B类任务的启动时间 Tia，Tib输入：1=Na，Nb=60，1=P=20 1=Tia，Tib=1000，1=Kia，Kib=50输出：各节点开始计算到任务完成的最少时间。,输入文件hpc.in5 5315 10 6 470 100 7 230 70 1 6输出文件hpc.out 93,一种可行的方案：时间：93节点1：BBBABB（10+4*9+15+6+10+4*4）节点2：节点3：AAAAA(30+1
40、*25),另一种可行的方案：时间：93节点1：BBBABB节点2：A节点3：AAAA,分析P=1的情况,a个A类任务，b个B类任务，分两种情况讨论：1.最后处理任务A 2.最后处理任务B,总时间=最后处理的是B类任务所需的最短时间+kax2+ta,总时间=最后处理的是A类任务所需的最短时间+kbx2+tb,P=1时，状态转移方程,设：ga(a,b)表示处理a个A类任务，b个B类任务，且最后处理的是A类任务所需的最短时间。gb(a,b)表示处理a个A类任务，b个B类任务，且最后处理的是B类任务所需的最短时间。根据上面的讨论，可以得到：ga(a,b)=min(1xa)gb(a x,b)+kax2+
41、tagb(a,b)=min(1xb)ga(a,b x)+kbx2+tb,设：g(a,b)表示处理a个A类任务，b个B类任务所需的最短时间。这个问题可以分解为最后处理任务A或最后处理任务B两种情况。g(a,b)=minga(a,b),gb(a,b),p 1,P1的情况：,第一个节点负责了i个任务A和j个任务B，则剩下的a i个任务A和b j个任务B都必须由后p 1个节点完成。设f(p,a,b)表示在后p个节点上处理a个A类任务，b个B类任务所需的最少时间。有：f(p,a,b)=min(0ia,0jb)maxg(i,j),f(p 1,a i,b j),总结：,由于计算f(p)时，只需用到f(p 1
42、)的结果，故可以使用滚动数组。这样，计算过程中，只需保存ga,gb,g,f(p 1),f(p)这5个大小为n2的数组，故空间复杂度是O(n2)。计算数组g的复杂度为O(n3)，一共有p个节点，故时间复杂度是O(pn3)。计算数组f的复杂度为O(pn4)。所以，总的时间复杂度为O(pn4)。在这个例子中，我们用f来表示目标问题。在求f之前，先要求出g，而在求g的时候，也采用了动态规划。我们称之为多次动态规划。很多题目中，动态规划并不是单一出现的，但有些例子中，这种多层次的结构并不明显，下一个例子将讨论这个问题。,交叉匹配,描述：两行正整数。第一行中有一个数和第二行中的一个数都为r，将这两个数用线
43、段连起来。称这条线段为r匹配线段。例如下图就显示了一条3匹配线段和一条2匹配线段。,对于给定的输入，找到画出最多的匹配线段的方式，使得：1）每条a匹配线段恰好和一条b匹配线段相交，且ab，a,b指代任何值，并非特定值。2）不存在两条线段都从一个数出发。计算出匹配线段的最多个数。,分析：,an：存储第一行的数 bm：存储第二行的数设 f(i,j)：表示如下图所示的两行数据，可以画出的最多的匹配线段数。,3.ai和bj处，各引出一条匹配线段，这时必须aibj。设ai=bv，bj=au。从ai向bv，bj向au各引一条匹配线段，这两条线段必然相交。这种情况的解即为f(u 1,v 1)+2。,该算法的
44、复杂度：O(nm)2)。,优化？,从什么地方入手呢？是否要改变思路？有更好的状态转移方程吗？,从问题的特性入手！,如果存在au=bj，且u u i，则用bj向au的匹配线段，代替bj向au的匹配线段，所得到的解不会变差。因此，u的选择是越靠后越好。同理，v的选择也是越靠后越好。,对于确定的i和j，相应的u和v的值也是确定的，这些值可以预先求出。而求法也是利用动态规划。设相应u和v的值分别为ui,j和vi,j。,这样，原动态转移方程可变为：,该算法需要保存f，u，v等数组，空间复杂度是O(nm)。计算f，u，v的时间复杂度是O(nm)，因此总的时间复杂度也还是O(nm)。,Codes(IOI 1
45、999),1.码字集合 2.一个文本，码字埋藏在文本之中求文本能覆盖的码字长度之和最大。要求：所有项目中的覆盖序列互相没有重叠；每个项目中的覆盖序列长度不超过（）1000,条件：1N100，N是码字的总数 每个码字的最大长度为100个字符 1=文本长度=1000000 对于文本中的任何位置，包含该位置的“右侧最小”覆盖序列总数不超过（）2500“右侧最小”覆盖序列的总数不超过（）10000,码字：RuN RaBbit HoBbit Stop文本：StXRuYNvRuHoaBbvizXztNwRRuuNNP,答案如下：12 2 9 21 RaBbit 1 4 7 RuN 1 24 28 RuN,
46、最简覆盖序列,给定一个字码，以及它的一个覆盖序列c，若c的任何连续子序列p都不是w的覆盖序列，则称c是w的最简覆盖序列。例如，ALAL和AAALAL都是ALL的一个覆盖序列，其中ALAL是ALL的最简覆盖序列，但AAALAL却不是ALL的最简覆盖序列。显然，一个字码的最简覆盖序列必然是它的右侧最小覆盖序列，反之则不然。若一个项的覆盖序列是其对应字码的最简覆盖序列，则称之为最简项。,结果总可以由若干最简项构成。这样，我们只要从文本中找到所有最简项即可！,问题转化为：首先必须要求出所有的最简项！,怎样求最简项？,最简项的总数不会超过10000，因此，可以用一个长为10000的线性表Items保存找
47、到的所有项：TItem=record(项类型)which:Byte;字码编号 st,ed:Longint覆盖序列的首尾位置end;Items:array1.10000 of TItem;m:Integer;文本中项的总数由于文本可能达到1M，我们最好只读一遍文件便求出Items。,定义：Leni表示第i个字码的长度。Wordsi：表示第I个字码。则Wordsi，1.Wordsi,j 表示第i个字码的前j个字符所构成的子串。Matchi,j：表示在当前已经读过的文本中，Wordsi,1.j对应的最简覆盖序列的首位置。若存在多个这样的覆盖序列，则Matchi,j的值为首位置最大的一个；若不存在这样
48、的覆盖序列，则Matchi,j为-。例如，若Words1=abcd，当前所读到的文本是aubcavbc，因为子串abc(即Words1,1.3)在当前所读到的文本中，最简覆盖序列有aubc和avbc，它们的首位置分别是1和5，因此Match1,3=5。如果当前读到了文本的第Index个字符Ch，而第i个字码的第j个字符也是Ch，则有下面3种情况：若j=1，这时令Matchi,1:=Index；若j1，则若Index-Matchi,j-1+11000(项中的覆盖序列长度不超过1000)，由于Wordsi,1.j和Wordsi,1.j-1在当前所读到的文本中，最简覆盖序列的最大首位置应该是相同的，
49、因此有Matchi,j:=Matchi,j-1。为了不产生非最简项，令Matchi,j-1:=-；若j=Leni且Index-Matchi,j+11000，则产生了一个项，且该项which:=i;st:=Matchi,j;ed:=Index。同时，令Matchi,j=-。,为了便于实现上述算法，我们建立一个字符表记录每个字符在字码集合中的位置，由于字码最多共有100*100个字符，因此该表的长度不超过10000。数组Chs的定义如下：TChar=recordCh:Char;字符i,j:Byte;该字符所在字码编号和在该字码中的位置end;Chs:array1.10000 of TChar;为了
50、便于检索，我们将Chs以关键字Ch按照字典顺序排序。由于在第二种情况中，Matchi,j利用了Matchi,j-1的信息。因此，若关键字Ch相同，则以关键字j按照降序排列。设Startx表示排序后Chs中第一个Ch值为x的元素的位置，则字符x在字码集合中出现的位置被记录在Chs的Startx到StartSucc(x)-1之中。,这样，找所有的项的算法为：,该算法结束后，Items中保存了所有的项，且项根据对应的覆盖序列的尾位置按照非降序排列。,通过动态规划求出结果,图G是有向无环图。求有向无环图的最长路径。设Fi表示V0到Vi的最长路径的长度。Fi:=MaxFj+LenItemsi.Which
