资源预览内容
第1页 / 共43页
第2页 / 共43页
第3页 / 共43页
第4页 / 共43页
第5页 / 共43页
第6页 / 共43页
第7页 / 共43页
第8页 / 共43页
第9页 / 共43页
第10页 / 共43页
亲,该文档总共43页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
动态规划的优化方法YALI 朱全民动态规划优化的内涵u动态规划算法的时间复杂度=阶段数*每个阶段状态转移的状态数*每次状态转移的时间或者:状态总数*每次状态转移的时间u重点:减少每个阶段的状态数,也就是减少 了状态总数优化方法1:改进状态的表示u例1:理想收入问题u理想收入是指在股票交易中,以1元为本金 可能获得的最高收入,并且在理想收入中 允许有非整数股票买卖。u已知股票在第i天每股价格是Vi元, 1iM,求M天后的理想收入。方法一u设Fi表示在第i天收盘时能达到的最高收 入,则有Fi的递推关系式:公式含义:在第i天收盘时能达到的最高的收 入,是将第j天收盘后的收入,全部用于买入 第k天的股票,再在第i天将所持的股票全部 卖出所得的收入。 时间复杂度是O(M3)。 方法二u设Pi表示前i天能获得的最多股票数,则 可列出状态转移方程:u设Qi表示前i天能达到的最大收入,则可 列出状态转移方程: 时间复杂度是O(M2)。方法三u分析:上述公式的含义是当0bi,则则用bi替换换bj 若在对对尾,则则直接插入u显显然该该算法的时间时间 复杂杂度为为O(n*log(n)例4:最大子序和问题描述输入一个长度为的整数序 列(A1,A2,An),从中找出 一段连续的长度不超过M的子序 列,使得这个序列的和最大。最大子序和输入一个长度为的整数序列(A1,A2,An),从中 找出一段长度不超过m的连续的子序列,使得这个序列的和 最大。例如:序列 1, -3, 5, 1, -2, 3当M=2或3时,S=5+1=6当M=4时,S=5+1-2+3=7数据范围:50%的数据N,M=S(j),则我们可以删掉S(i)( 因为S(i)永远不会被用到)。此时的队列 中的元素构成了一个单调递增的序列,即 :S1=i-m为 止。若当前队尾元素S(k)=S(i-1),则S(k) 出队;直到S(k)tp+1,j 与情况1是对称的。方法4:利用贪心思想减少状态总数u例6:快餐问题uPeter最近在R市开了一家快餐店,为了招揽顾客,该快餐店 准备推出一种套餐,该套餐由A个汉堡,B个薯条和C个饮料 组成。价格便宜。为了提高产量,Peter从著名的麦当劳公司 引进了N条生产线。所有的生产线都可以生产汉堡,薯条和饮 料,由于每条生产线每天所能提供的生产时间是有限的、不同 的,而汉堡,薯条和饮料的单位生产时间又不同。这使得 Peter很为难,不知道如何安排生产才能使一天中生产的套餐 产量最大。请你编一程序,计算一天中套餐的最大生产量。为 简单起见,假设汉堡、薯条和饮料的日产量不超过100个。u输入:第一行为三个不超过100的正整数A、B、C中间以一个 空格分开。第二行为3个不超过100的正整数p1,p2,p3分别 为汉堡,薯条和饮料的单位生产耗时。中间以一个空格分开。 第三行为N(0size,lsize) ,那么肯定u无论如何Ci/Bi最小的那些房间肯定会被选到。u于是我们可以贪心在ksize,lsize的时候,给 他们安排Ci/Bi最小的房间。u然后再进行动态规划。u由于BiM时,可带任意个辅 词后缀)的最优分解方案下划分的句子数与单词数;F(u,i):表示将L的前i个字符划分为以名词结尾(当iM;F(u,i)=min F(u,j)+(1,1), L(j+1.i)为名词;F(v,j)+(0,1), L(j+1.i)为名词;F(u,j)+(0,1), L(j+1.i)为辅词,iy,下面仅讨论zy,zy的情况是类似的。u由izyj有: 证明u用数学归纳法证明函数m也满足四边形不等式。对四边形 不等式中“长度”l=j-i进行归纳:u当i=i或j=j时,不等式显然成立。由此可知,当l1时 ,函数m满足四边形不等式。u下面分两种情形进行归纳证明: 情形1:ij。下面只讨论kj,kj的情况 是类似的。u情形2:iy。u情形2.1,当zyjj时:情形情形2.22.2,当,当i-1i-1yzji-1i-1yzj时:时:u令si,j=k,(ij),最后,我们证明决策si,j满足单调性。u令mki,j=mi-1,k+wk+1,j;u我们先来证明si-1,jsi,j,只要证明对于所有ikkj且 mki-1,jmki-1,j,有:mki,jmki,j。u类似地,我们可以证明一个更强的不等式mki-1,j-mki-1,jmki,j-mki,jmki-1,j+mki,jmki,j+mki-1,ju利用递推定义式展开整理的:mi-2,k+mi-1,kmi- 1,k+mi-2,k,这就是i-2i-1kk时m的四边形不等式 。u我们再来证明si,jsi,j+1,设kkj,则我们只需证明一个更强的不等式: mki,j-mki,jmki,j+1-mki,j+1u也就是mki,j+mki,j+1mki,j+1+mki,ju利用递推定义式展开整理的: wk+1,j+wk+1,j+1wk+1,j+1+wk+1,j,这就是k+1k+1jj+1时w的四边形不等式。u综上所述,该问题的决策si,j具有单调性,因此u优化后的算法时间复杂度为O(n*p)。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号