动态规划pptPPT讲稿.ppt

《动态规划pptPPT讲稿.ppt》由会员分享，可在线阅读，更多相关《动态规划pptPPT讲稿.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划ppt第1页，共50页，编辑于2022年，星期五简介动态规划简称DP，是在20世纪50年代由一位卓越的美国数学家RichcardBellman发明的。它作为一种重要的工具在应用数学中被广泛的应用。它不仅可以解决特定类型的优化问题，还可以作为一种通用的算法设计技术来使用。第2页，共50页，编辑于2022年，星期五DP的实质利用问题的所具有的重叠子问题的性质进行记忆化求解。（用空间换时间）第3页，共50页，编辑于2022年，星期五求Fibonacci数：f(n)=f(n-1)+f(n-2)n2f(1)=f(2)=1第4页，共50页，编辑于2022年，星期五常规递归intNon_DP(int

2、n)if(n=1|n=2)return1;elsereturnNon_DP(n-1)+Non_DP(n-2);指数级时间复杂度，无法忍受第5页，共50页，编辑于2022年，星期五两种实现方式自底向上(bottomup)intDP_Bottom_Up(intn)memo1=memo2=1;for(inti=3;i=n;i+)memoi=memoi-1+memoi-2;returnmemon;第6页，共50页，编辑于2022年，星期五自顶向下（topdown）（这样写法也叫记忆搜索）intDP_Top_Down(intn)if(n=1|n=2)return1;if(memon!=0)returnm

3、emon;memon=DP_Top_Down(n-1)+DP_Top_Down(n-2);returnmemon;第7页，共50页，编辑于2022年，星期五基本概念最短路问题AB1B2C1C2C3C4D1D2D3E求A到E的最短路径。第8页，共50页，编辑于2022年，星期五直观的方法是用回溯法搜索。时间复杂度为指数级。低效的原因：没有充分利用重叠子问题的性质。第9页，共50页，编辑于2022年，星期五此图有明显的次序，可以划分为5阶段。AB1B2C1C2C3C4D1D2D3E阶段0阶段1阶段2阶段3阶段4第10页，共50页，编辑于2022年，星期五设Diskx为第k阶段城市x到城市E的最短路

4、径长度。mapij为i，j两个城市间的距离。递归方程为Diskx=minDisk+1y+mapx,y此问题时间复杂度降为O(n2).第11页，共50页，编辑于2022年，星期五状态：贴切，简洁的描述出事物性质的单元量。例如：Disx。要求：状态与状态之间可以转移，以便有初始状态逐渐转移到目标状态，找到问题的解。阶段：若干性质相近可以同时处理的状态的集合。就是计算状态的顺序。要求：每个阶段中状态的取值只与这个阶段之前的阶段中的状态只与这个阶段之前的阶段中的状态有关有关，与这个阶段之后的阶段中的状态无关。第12页，共50页，编辑于2022年，星期五状态转移方程：前一个阶段中的状态转移到后一个阶段的

5、状态得演变规律，即相邻两个阶段的状态变化方程。fk(i)=optfk-1(j)+cost(i,j)k阶段的i状态与k-1阶段的j状态有关决策：计算每个状态时作出的选择。第13页，共50页，编辑于2022年，星期五无后效性：决策之取决于当前状态的特征因素，而和到达此状态的方式无关。也就是每个阶段中状态的取值只与这个阶段之前的阶段中的状态有关，与这个阶段之后的阶段中的状态无关。如果当前定义的状态不满足无后效性，应重新定义。第14页，共50页，编辑于2022年，星期五一维状态存储问题硬币问题1：有n种硬币，每种硬币的面值为vi元，且只有一枚，问用这n种硬币找零S元的方法数。设dij为前i种硬币组成j

6、元的方法数。dij=di-1j+di-1j-vid00=1,d01S=0空间复杂度为O(n2),浪费！第15页，共50页，编辑于2022年，星期五d0=1;d1S=0;for(i=1;i=vi;j-)dj+=dj-vi;第16页，共50页，编辑于2022年，星期五0-1背包问题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大?第17页，共50页，编辑于2022年，星期五设m(i,j)是背包容量为j，可选择物品为i，i+1，,n时，0-1背包问题的最优值。m(i,j)=maxm(i+1,j),m(i+1,j-w

7、i)+vij=wim(i+1,j)0=j=wn00=jwn第18页，共50页，编辑于2022年，星期五d0c=0;for(i=1;i=wi;j-)dj=max(dj,dj-wi+vi);第19页，共50页，编辑于2022年，星期五推荐题目：http:/poj.org/problem?id=1384Piggy-Bank第20页，共50页，编辑于2022年，星期五硬币问题2：有n种硬币，每种硬币的面值为vi元，有mi枚，问用这n种硬币找零S元的方法数。第21页，共50页，编辑于2022年，星期五d0=1;d1S=0;for(i=1;i=vi;j-)for(k=1;k=0)dj+=dj-k*vi;第

8、22页，共50页，编辑于2022年，星期五硬币问题3：有n种硬币，每种硬币的面值为vi元，有无数枚，问用这n种硬币找零S元的方法数。第23页，共50页，编辑于2022年，星期五d0=1;d1S=0;for(i=1;i=vi;j-)for(k=1;k+)if(j-k*vi=0)dj+=dj-k*vi;elsebreak;第24页，共50页，编辑于2022年，星期五d0=1;d1S=0;for(i=1;i=n;i+)for(j=vi;j=S;j+)/无数的时候是顺向dj+=dj-vi;第25页，共50页，编辑于2022年，星期五推荐题目：http:/ Event in HDUBig Event i

9、n HDU第26页，共50页，编辑于2022年，星期五http:/poj.org/problem?id=2614OldWineIntoNewBottles有n种小瓶子，每种瓶子容量范围是Vi1Vi2，要灌满容量为L的大瓶子。问最少差多少体积没有灌满。设di表示体积为i是否可以达到。若v可取到，则di=di|di-v第27页，共50页，编辑于2022年，星期五d0=1;d1L=0;for(i=0;in;i+)for(j=0;j=L-vi1;j+)if(dj=1)for(k=vi1;k=vi2;k+)dj+k=1;第28页，共50页，编辑于2022年，星期五最大子段和问题：给定由n个整数(可能为负

10、整数)组成的序列a1,a2,an，求该序列形如的子段和的最大值。第29页，共50页，编辑于2022年，星期五设bi为到ai截至且包括ai的字段最大和。intmaxsum()intsum=0,b=0;for(inti=0;i0)b+=ai;/正的就连接起来elseb=ai;/不然重新来过if(bsum)sum=b;/sum记录的一直是最大的值returnsum;第30页，共50页，编辑于2022年，星期五http:/ 9876再举一个例子(N=11)：1008999897675928354901第36页，共50页，编辑于2022年，星期五要用3条非升链：100898976755419992839

11、0而我们再观察一下它的最长升链，其中一条是：758390，长度也为3！第37页，共50页，编辑于2022年，星期五这是巧合还是必然？这是必然！可以证明非升链覆盖问题和最长升链问题是同解的。同样，升链覆盖、降链覆盖、非降链覆盖和最长非升链、最长非降链、最长降链同解。口诀：前面加“非”字大家可以想象证明，等大家了解了算法2，就自然明白了。第38页，共50页，编辑于2022年，星期五算法2：由于N的规模，算法一是在太慢了。这里介绍一种O(nlogn)的算法。首先定义数组D：Di（1=I=N）表示目前为止，所有长度为i的升链中，最后一个元素的最小可能值。如当前找到两个长度为3的升链：234；139那么

12、D3=4。显然，对于同样长度的升链，结尾越小越容易拓展成更长的升链。并且可知D是一个严格升链（若其中Di+1=numiand(p=0orDp1s，说明找到更长的链，更新s。第40页，共50页，编辑于2022年，星期五例如：132545initials=0step1s=1D1=1step2s=2D1=1D2=3step3s=2D1=1D2=2step4s=3D1=1D2=2D3=5step5s=3D1=1D2=2D3=4step6s=4D1=1D2=2D3=4D4=5第41页，共50页，编辑于2022年，星期五显然这个算法是O(nlogn)的。同样这个算法证明了前面讨论的变形的正确性。首先，本算

13、法实际上构造出了用最长升链长度（MAXL）条非升链覆盖这N个数的一组解。我们只需要证明至少要用MAXL条非升链才能完成覆盖即可，显然，最长升链就需要MAXL条降链覆盖。证毕。第42页，共50页，编辑于2022年，星期五推荐题目：http:/poj.org/problem?id=1631BridgingSignalshttp:/poj.org/problem?id=2336Ferry Ferry Loading IILoading II第43页，共50页，编辑于2022年，星期五二维状态存储问题矩阵连乘问题矩阵连乘问题（MCM）A(m*n)*B(n*q)cost=m*n*qA1(10 x100)

14、,A2(100 x5),A3(5x50)(A1(A2A3)=100 x5x50+10*100*50=75000(A1A2)A3)=10 x100 x5+10 x5x50=7500第44页，共50页，编辑于2022年，星期五最优子结构：第45页，共50页，编辑于2022年，星期五重叠子问题：第46页，共50页，编辑于2022年，星期五第47页，共50页，编辑于2022年，星期五阶段划分：第48页，共50页，编辑于2022年，星期五推荐题目：http:/poj.org/problem?id=1141BracketsSequence第49页，共50页，编辑于2022年，星期五谢谢第50页，共50页，编辑于2022年，星期五