《线性类动态规划.ppt》由会员分享，可在线阅读，更多相关《线性类动态规划.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最长上升序列 w设有整数序列b1,b2,b3,bm，若存在下标i1i2i3 in，且bi1bi2bi3 bin，则称 b1,b2,b3,bm中有长度为n的上升序列bi1,bi2,bi3,bin。w求序列b1,b2,b3,bm中所有长度(n)最大上升子序列w输入：整数序列。w输出：最大长度n和所有长度为n的序列个数。分析w设设f f(i)为前为前i个数中的最长上升序列长度个数中的最长上升序列长度,则则wf(i)=maxf(j)+1 f(i)=maxf(j)+1 (1=ji(1=ji=m=m,bjbjbi)bi)w边界为边界为F(1)=1F(1)=1分析w设设t t(i)(i)为前为前i i个数中
2、最长不下降序列的个数个数中最长不下降序列的个数,则则wt(i)=t(j)(t(i)=t(j)(1=ji1=ji=m,bjbi,f(i)=f(j)+1)=m,bjbi,f(i)=f(j)+1)w初始为初始为t t(i)=1(i)=1w当当f(i)=nf(i)=n时，将时，将t(i)t(i)累加累加w举例：举例：1 2 3 4 6 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 t=4=4进一步(3)求本质不同的最长不下降序列个数有多少个？如：1 2 3 4 6 5 8 10 9 有，1 2 3 4 6 8
3、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改进算法w上上例例显显然然对对于于相相两两个个相相同同的的数数，重重复复算算了了多多次次因此，我们对算法进行改进：因此，我们对算法进行改进：w对对原原序序列列按按b b从从小小到到大大（当当bi=bi=bjbj时时按按F F从从大大到到小小）排排序序，增增设设Order(i)Order(i)记记录录新新序序列列中中的的i i个个数数在在
4、原原序列中的位置。可见，序列中的位置。可见，w求求 t(i)t(i)时时，当当 f f(j)=f(j+1),b(j)=b(j+1)(j)=f(j+1),b(j)=b(j+1)且且Order(j+1)Order(i)Order(j+1)Order(i)时时，便便不不累累加加t(j)t(j)。这这样样就避免了重复。就避免了重复。w 上述算法的时间复杂度为上述算法的时间复杂度为O(n2)添括号问题 w有有一一个个由由数数字字1 1，2 2，.，9 9组组成成的的数数字字串串（长长度度不不超超过过200200），问问如如何何将将M(M=20)M(M=20)个个加加号号(+)(+)插插入入到到这这个个数
5、数字字串串中中，使使所所形形成成的的算算术术表表达达式式的的值值最最小小。请请编编一一个个程程序序解决解决这这个个问题问题。w注意：注意：w加号不能加在数字串的最前面或最末尾，也不应有两个加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。或两个以上的加号相邻。wM M保证小于数字串的长度。保证小于数字串的长度。w例如：数字串例如：数字串7984679846，若需要加入两个加号，则最佳方，若需要加入两个加号，则最佳方案为案为79+8+4679+8+46，算术表达式的值，算术表达式的值133133。分析w考虑到数据的规模超过了长整型考虑到数据的规模超过了长整型,我们注意在解题过
6、程中我们注意在解题过程中采用高精度算法采用高精度算法.w规划方程规划方程:wFI,J=MIN FI-1,K+NUMK+1,J (I-FI,J=MIN FI-1,K+NUMK+1,J (I-1=K=J-1)1=K=J-1)w边界值边界值:F0,I:=NUM1,I:F0,I:=NUM1,I;wFIFI，JJ表示前表示前J J个数字中添上个数字中添上I I个加号后得到的最小值。个加号后得到的最小值。wNUMINUMI，JJ表示数字串第表示数字串第I I位到第位到第J J位的数位的数w上述问题的每一步，都只与上一步有关。因此可以采用上述问题的每一步，都只与上一步有关。因此可以采用滚动数组滚动数组w程序
7、的时间效率约为程序的时间效率约为 20*200*20*200*200200 演唱会w一场演唱会即将举行。现有一场演唱会即将举行。现有N（ON=200）个）个歌迷排队买票，一个人买一张，而售票处规定，歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第一个人每次最多只能买两张票。假设第I位歌迷位歌迷买一张票需要时间买一张票需要时间Ti（1=I=n），队伍中相），队伍中相邻的两位歌迷（第邻的两位歌迷（第j个人和第个人和第j+1个人）也可以由个人）也可以由其中一个人买两张票，而另一位就可以不用排其中一个人买两张票，而另一位就可以不用排队了，则这两位歌迷买两张票的时间变为队了，
8、则这两位歌迷买两张票的时间变为Rj，(假如假如RjTj+Tj+1，则这样做就可以缩短后面歌，则这样做就可以缩短后面歌迷等待的时间，加快整个售票的进程迷等待的时间，加快整个售票的进程)。w现给出现给出N，Ti和和Ri，求使每个人都买到票的最短，求使每个人都买到票的最短时间和方法。时间和方法。分析w设f（i）为前i个人花费最短时间w于是有f（i）=minf（i-1）+Ti，f（i-2）+Ri-1，w初始f（0）=0，f（1）=T1复制书稿w假设有M本书（编号为1，2，M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，PM）。w任务：将这M本书分给K个抄写员(K=M)每本书只能分配给一
9、个抄写员进行抄写，而每个抄写员所分配到的书必须是连续顺序的。分析w设F（I，J）为前I个抄写员复制前J本书的最小“页数最大数”。w于是有 F（I，J）=MINmax F（I-1，V），T（V+1，J）（1=I=K，I=J=M-K+I，I-1=V=J-1。其中T（V+1，J）表示从第V+1本书到第J本书的页数和。起步时F（1，1）=P1。多米诺骨牌 w有一种多米诺骨牌是平面的，其正面被分成上下两部分，有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上每一部分的表面或者为空，或者被标上1至至6个点。个点。w现有一行排列在桌面上：例如，顶行骨牌的点数之和为现有一行排
10、列在桌面上：例如，顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为；底行骨牌点数之和为1+5+3+2=11。顶行和。顶行和底行的差值是底行的差值是2。这个差值是两行点数之和的差的绝对。这个差值是两行点数之和的差的绝对值。值。w每个多米诺骨牌都可以上下倒置转换，即上部变为下部，每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。下部变为上部。w现在的任务是，以最少的翻转次数，使得顶行和底行之现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。间的差值最小。分析w以骨牌序列上下两部分的差值I作为状态，把达到这一状态的翻转步数作为状态值，记为f（I）。w于是有 f（I
11、）=minf（I+J）+1（-12=J=12,J为偶数，且要求当前状态有差值为J/2的骨牌）。w这里，I不是无限增大或减小，其范围取决于初始骨牌序列的数字差的和的大小。系统可靠性 w一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？w给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。w输入文件格式：第一行：n C第二行：C1 P1
12、(0)P1(1)P1(X1)（0=X1=C/Ck）第 n 行：Cn Pn(0)Pn(1)Pn(Xn)（0=Xn=C/Cn）分析w例：输入：例：输入：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.6375w设设FI,moneyFI,money表表示示将将moneymoney的的资资金金用用到到前前I I项项备备用用件件中中去去的最大可靠性，则有的最大可靠性，则有 FI,money=maxFI-1,moneyk*CostI FI,money=maxFI-1,moneyk*CostI (0=I=n,
13、(0=I=n,0=0=K K=money div Cost(I)=money div Cost(I)w初始：初始：F0F0,0,0=0=0w目标：目标：FnFn,C,C=0=0航空旅行w给定一张航空图，图中的顶点代表城市，边代表两城市给定一张航空图，图中的顶点代表城市，边代表两城市的直通航线。现要求找出一条满足下述限制条件的、含的直通航线。现要求找出一条满足下述限制条件的、含城市最多的旅游路线：城市最多的旅游路线：w1.从最西的一个城市出发，单方向从西向东途经若干城从最西的一个城市出发，单方向从西向东途经若干城市到达最东的一个城市，然后再单方向从东向西飞回起市到达最东的一个城市，然后再单方向从
14、东向西飞回起点（可途经若干城市）；点（可途经若干城市）；w2.除起点城市外，任何城市只能访问一次，起点城市被除起点城市外，任何城市只能访问一次，起点城市被访问两次：出发一次，返回一次。访问两次：出发一次，返回一次。分析w设fi,j表示顶点i至顶点N与顶点j至顶点N的两条路线的最多顶点数，很容易得出，fN,N=1,fi,N=2（当该阶段中顶点i与顶点N间有直通航线），ai,j=aj,i。这样，可以得到以下关系式：wfi,j=maxfk,j+1,fi,j (kj且边(k,i)存在且ak,j0)w时间复杂度为O(N3)积木游戏 w有有N块长方体积木，编号依次为块长方体积木，编号依次为1,2,N。第。
15、第i块长宽高分块长宽高分别为别为ai,bi,ci（i=1,2,N），），w要从中选出若干块，将他们摞成要从中选出若干块，将他们摞成M（1=M=N=n），），x,y是上面一块积木接触是上面一块积木接触面的两条边（面的两条边（x=y），），则一定满足则一定满足m.=x和和n=y；w下面的积木的编号要小于上面的积木的编号。下面的积木的编号要小于上面的积木的编号。w请你编一程序，寻找一种游戏方案，使得所有能摞成的请你编一程序，寻找一种游戏方案，使得所有能摞成的M根柱子的高度之和最大。根柱子的高度之和最大。分析w设设（1）fi,j,k表示以第表示以第i块积木的第块积木的第k面为第面为第j根柱子的顶面的最
16、优方案的根柱子的顶面的最优方案的高度总和；高度总和；（2）blocki,k 记录每个积木的三条边信息（记录每个积木的三条边信息（blocki,4:=blocki,1;blocki,5:=blocki,2）。）。其中其中blocki,j+2表示当把第表示当把第i块积木的第块积木的第j面朝上时所对应的高，即所增加的高度；面朝上时所对应的高，即所增加的高度；（3）cani,k,p,kc表示第表示第I块积木以其第块积木以其第k面朝上，第面朝上，第p块积木以第块积木以第kc面面朝上时，能否将积木朝上时，能否将积木I放在积木放在积木p的上面。的上面。1表示能，表示能，0表示不能。对表示不能。对于于fi,j
17、,k,有两种可能：有两种可能：1.除去第除去第i块积木，第块积木，第j根柱子的最上面的积木为编号为根柱子的最上面的积木为编号为p的，若第的，若第p块积木以第块积木以第kc面朝上，必须保证当第面朝上，必须保证当第I块积木以块积木以k面朝上时能够被放面朝上时能够被放在上面，即在上面，即cani,k,p,kc=1；2.第第i块积木是第块积木是第j根柱子的第一块积木，第根柱子的第一块积木，第j-1根柱子的最上面为第根柱子的最上面为第p块积木，则此时第块积木，则此时第p块积木可以以任意一面朝上。块积木可以以任意一面朝上。动态规划w边界条件：wf1,1,1:=block1,1,3;f1,1,2:=bloc
18、k1,1,4;f1,1,3:=block1,1,5;wfi,0,k:=0;(1=i=n,1=k=3);w时间复杂度为O(n2*m)石子合并 w在一园形操场四周摆放在一园形操场四周摆放N堆石子堆石子(N100),现要将石现要将石子有次序地合并成一堆子有次序地合并成一堆.规定每次只能选相临的两规定每次只能选相临的两堆合并成一堆堆合并成一堆,并将新的一堆的石子数并将新的一堆的石子数,记为该次合记为该次合并的得分。编一程序并的得分。编一程序,由文件读入堆数由文件读入堆数N及每堆石子及每堆石子数数(20),(1)选择一种合并石子的方案选择一种合并石子的方案,使得做使得做N-1次合并次合并,得得分的总和最
19、少分的总和最少(2)选择一种合并石子的方案选择一种合并石子的方案,使得做使得做N-1次合并次合并,得分的总和最大得分的总和最大示例贪心法 N=5 石子数分别为3 4 6 5 4 2。用贪心法的合并过程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24总分：62然而仔细琢磨后，发现更好的方案：第一次3 4 6 5 4 2得分 7第二次7 6 5 4 2得分13第三次13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24总分：61显然，贪心法是错误的。动态
20、规划 w用datai,j表示将从第i颗石子开始的接下来j颗石子合并所得的分值，wmaxi,j表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：wmaxi,j=max(maxi,k+maxi+k,j k+datai,k+datai+k,jk)(2=k=j)wmaxi,1=0w同样的，我们用mini,j表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：wmini,j=min(mini,k+mini+k,j k+datai,k+datai+k,j k)(0=k=j)wmini,0=0w这样，我们完美地解决了这道题。时间复杂度也是O(n2)。多边形多边形 w多多
21、角角形形是是一一个个单单人人玩玩的的游游戏戏，开开始始时时有有一一个个N N个个顶顶点点的的多多边边形形。如如图图，这这里里N=4N=4。每每个个顶顶点点有有一一个个整整数数标标记记，每每条条边边上上有有一一个个“+”+”号号或或“*”“*”号。边从号。边从1 1编号到编号到N N。第第一一步步，一一条条边边被被拿拿走走；随随后后各各步步包括如下：包括如下：w选选择择一一条条边边E E和和连连接接着着E E的的两两个个顶顶点点V1V1和和 V2V2；w得得到到一一个个新新的的顶顶点点，标标记记为为V1V1与与V2V2通过边通过边E E上的运算符运算的结果。上的运算符运算的结果。w最最后后，游游
22、戏戏中中没没有有边边，游游戏戏的的得得分分为仅剩余的一个顶点的值。为仅剩余的一个顶点的值。样例写一个程序，对于给定一个多边形，计算出可能写一个程序，对于给定一个多边形，计算出可能的最高得分，并且列出得到这个分数的过程。的最高得分，并且列出得到这个分数的过程。分析 分析w我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值 w用f(i,j)表示从j开始，进行i次删边操作所能得到的最大值，num(i)表示第i个顶点上的数，若为加法，那么：进一步分析w最后，我们允许顶点上出现负数。以前的方程还适不适最后，我们允许顶点上出现负数。以前的方程还适不适用呢？用呢？w这这个个例例子子的的最最优优解
23、解应应该该是是（3+23+2）*（-9-9）*（-5-5）=250=250，然然而而如如果果沿沿用用以以前前的的方方程程，得得出出的的解解将将是是（-10-10）*3+23+2）*（-5-5）=140=140。为什么？。为什么？w我们发现，两个负数的积为正数；这两个负数越小，它我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。大，而从来没有想过负数的积为正数这个问题。-932-5*图六+最终？w我们引入函数我们引入函数fminfmin和和fmaxfmax来解决
24、这个问题。来解决这个问题。fmax(i,jfmax(i,j)表示从表示从j j开始，进行开始，进行i i次删边操作所能得次删边操作所能得到的最大值，到的最大值，fmin(i,jfmin(i,j)表示从表示从j j开始，进行开始，进行i i次删次删边操作所能得到的最小值边操作所能得到的最小值 。当当OP=+OP=+Fmax(i,jFmax(i,j)=maxfmax(i,k)+fmax(k+1,j)=maxfmax(i,k)+fmax(k+1,j)Fmin(i,jFmin(i,j)=minfmin(i,k)+fmin(k+1,j)=minfmin(i,k)+fmin(k+1,j)完美解决w初始初始
25、值值 Fmax(i,iFmax(i,i)=)=num(inum(i)Fmin(i,iFmin(i,i)=)=num(inum(i)w到到此此为为止止，整整个个问问题题圆圆满满解解决决了了。算算法法的的空空间间复复杂杂度度为为O(nO(n2 2)，算算法法时时间间复复杂杂度度为为O O(n(n4 4)()(先先要要枚枚举举每每一一条条边边，然然后后再再用用复复杂杂度度为为O(nO(n3 3)的的动态规动态规划解决）。划解决）。Blocks wJimmyJimmy最近迷上了一款叫做方块消除的游戏最近迷上了一款叫做方块消除的游戏.游戏规则游戏规则如下：如下：n n个带颜色方格排成一列，相同颜色的方块
26、连成个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻的方块颜色相同，则这两个方一个区域（如果两个相邻的方块颜色相同，则这两个方块属于同一个区域块属于同一个区域).).游戏时，你可以任选一个区域消游戏时，你可以任选一个区域消去去.设这个区域包含的方块数为设这个区域包含的方块数为x,x,则将得到则将得到x x2 2的分值的分值.方方块消去之后，右边的方格将向左移动块消去之后，右边的方格将向左移动.w虽然游戏很简单，但是要得到高分也不是很容易虽然游戏很简单，但是要得到高分也不是很容易.Jimmy.Jimmy希望你帮助他找出最高可以得到多少分希望你帮助他找出最高可以得到多少分wN200.
27、N200.Samplew如图，依次消去灰,白,黑区域，你将得到42+32+22=29分，这是最高得分.算法分析w合并颜色序列，如 1 1 1 3 3 2 4 4 4 5 5 根据方块消除的规则，连在一起的相同颜色方块可以合并 上面的颜色序列为(1,3),(3,2),(2,1),(4,3),(5,2),其中(a,b)表示有b个颜色为a的连在一起.w于是题目可以表示成colori,leni,1=i=m,m表示颜色序列总共有m段.上面的颜色序列中,m=5,wcolor1.5=(1,3,2,4,5)wlen 1.5=(3,2,1,3,2)w定义状态w设S(i,j,k)为(colori,leni),(c
28、olori+1,leni+1)(colorj-1,lenj-1)的连续同色整段以及在一系列消除操作后j后接了k个颜色为colorj的方块(colorj,lenj+k)的一个颜色序列.w设f(i,j,k)表示消除S(i,j,k)这一个颜色序列可以得到的最大分值.算法分析算法分析w动态规划转移w如果立刻将(colorj,lenj+k)这一段消除，则转移为f(i,j-1,0)+(lenj+k)2w如果lenj+k暂时不消除而连接到上一个颜色相同的块上,则转移为f(i,p,k+lenj)+f(p+1,j-1,0).其中colorp=colorj,i=pjw动态规划转移方程 f(i,j,k)=Maxf(i,j-1,0)+(lenj+k)2,f(i,p,k+lenj)+f(p+1,j-1,0)算法分析w初值 f(i,i-1,0)=0w答案 f(1,m,0)w时间复杂度 O(n4)w空间复杂度 O(n3)