动态规划讲解大全(含例题及答案)

1、动态规划讲解大全动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著DynamicProgramming,这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得

2、到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题

3、，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。基本模型多阶段决策过程的最优化问题。在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序

4、列，因而也就确定了整个过程的一条活动路线，如图所示：(看词条图)这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。记忆化搜索给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：(i,j)=ai,j+minf(i+1,j)，f(i+1,j+1)对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动

5、态规划就不是那么简单了。解决方法：我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的递归过程:f1:=f(i-1,j+1);f2:=f(i-1,j);iff1>f2thenf:=f1+ai,jelsef:=f2+ai,j;显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n,明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存放一个opt数组：Opti,j-每产生一个f(i,j)，将f(i,j)的值放入opt中，以后再次调用到f(i,j)的时候，直接从opti,j来取就可以了。于是动态规划的

6、状态转移方程被直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，避免了动态规划状态转移先后的问题，而且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常实用的.状态决策决策：当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。状态：我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态的最优值的。我们就从动态规划的要诀，也就是核心部分“状态”开始，来逐步了解动态规划。有时候当前状态确定后,以前状态就已经确定,则无需枚举.动态规划算法的应用近

7、年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。要了解动态规划的概念，首先要知道什么是多阶段决策问题。1. 多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个

8、效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.2动态规划问题中的术语阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。在前面的例子中，第一个阶段就是点A,而第二个阶段就是点A到点B,第三个阶段是点B到点C,而第四个阶段是点C到点D。状态：状态表示每个阶段开

9、始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶段某支路的终点。在前面的例子中，第一个阶段有一个状态即A,而第二个阶段有两个状态B1和B2,第三个阶段是三个状态C1,C2和C3,而第四个阶段又是一个状态D。过程的状态通常可以用一个或一组数来描述,称为状态变量。一般,状态是离散的,但有时为了方便也将状态取成连续的。当然,在现实生活中,由于变量形式的限制,所有的状态都是离散的,但从分析的观点,有时将状态作为连续的处理将会有很大的好处。此外,状态可以有多个分量(多维情形),因而用向量来代表；而且在

10、每个阶段的状态维数可以不同。当过程按所有可能不同的方式发展时,过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性

11、。决策：一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多间题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。给定k阶段状态变量x(k)的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态

12、变量x(k+1)也就完全确定，即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化，那么可以把这一关系看成(x(k),u(k)与x(k+1)确定的对应关系，用x(k+1)=Tk(x(k),u(k)表示。这是从k阶段到k+1阶段的状态转移规律,称为状态转移方程。最优性原理:作为整个过程的最优策略,它满足：相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略”。D也是B1到D的最短路径事实正是如此，因此我们认为这个例子满足最优性原理的要求。0C20C2是A到C2的最短路径，B10B10D,这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：A

13、0C20B10最优性原理实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到D,我们知道，最短路径是A动态规划练习题USACO2.2SubsetSums题目如下：对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于1,2,3能划分成两个子集合，他们每个的所有数字和是相等的：and1,2这是唯一一种分发(交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数)如果N=7,有四种方法能划分集合1,2,3,4,5,6,7，每一种分发的子集合各数字和是相等的:1,6,7and2,3,4,5注1+6+

14、7=2+3+4+52,5,7and1,3,4,63,4,7and1,2,5,61,2,4,7and3,5,6给出N,你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。PROGRAMNAME:subsetINPUTFORMAT输入文件只有一行,且只有一个整数NSAMPLEINPUT(filesubset.in)7OUTPUTFORMAT输出划分方案总数,如果不存在则输出0。SAMPLEOUTPUT(filesubset.out)4参考程序如下：#include<fstream>usingnamespacestd;constunsignedin

15、tMAX_SUM=1024;intn;unsignedlonglongintdynMAX_SUM;ifstreamfin("subset.in");ofstreamfout("subset.out");intmain()fin>>n;fin.close();ints=n*(n+1);if(s%4)fout<<0<<endl;fout.close();return;s/=4;inti,j;dyn0=1;for(i=1;i<=n;i+)for(j=s;j>=i;j-)dynj+=dynj-i;fout<&

16、lt;(dyns/2)<<endl;fout.close();return0;USACO2.3LongestPrefix题目如下：在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的(称之为元素的)序列很感兴趣。如果一个集合P中的元素可以通过串联(允许重复；串联，相当于Pascal中的“+”运算符)组成一个序列S，那么我们认为序列S可以分解为P中的元素。并不是所有的元素都必须出现。举个例子，序列ABABACABAAB可以分解为下面集合中的元素：A,AB,BA,CA,BBC序列S的前面K个字符称作S中长度为K的前缀。设计一个程序，输入一个

17、元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。PROGRAMNAME:prefixINPUTFORMAT输入数据的开头包括1.200个元素(长度为1.10)组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个“.”的行。集合中的元素没有重复。接着是大写字母序列S，长度为1.200,000，用一行或者多行的字符串来表示，每行不超过76个字符。换行符并不是序列S的一部分。SAMPLEINPUT(fileprefix.in)AABBACABBCABABACABAABCOUTPUTFORMAT只有一行，输出一个整数，表示S能够分

18、解成P中元素的最长前缀的长度。SAMPLEOUTPUT(fileprefix.out)11示例程序如下：#include<stdio.h>#defineMAXP200#defineMAXL10charprimMAXP+1MAXL+1;intnump;intstart200001;chardata200000;intndata;intmain(intargc,char*argv)FILE*fout,*fin;intbest;intlv,lv2,lv3;if(fin=fopen("prim.in","r")=NULL)perror("f

19、openfin");exit(1);if(fout=fopen("prim.out","w")=NULL)perror("fopenfout");exit(1);while(1)fscanf(fin,"%s",primnump);if(primnump0!='.')nump+;elsebreak;ndata=0;while(fscanf(fin,"%s",data+ndata)=1)ndata+=strlen(data+ndata);start0=1;best=0;fo

20、r(lv=0;lv<ndata;lv+)if(startlv)best=lv;for(lv2=0;lv2<nump;lv2+)for(lv3=0;lv+lv3<ndata&&primlv2lv3&&primlv2lv3=datalv+lv3;lv3+);if(!primlv2lv3)startlv+lv3=1;if(startndata)best=ndata;fprintf(fout,"%in",best);return0;USACO3.1ScoreInflation题目如下：我们试着设计我们的竞赛以便人们能尽可能的多得分,

21、这需要你的帮助。我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间,M(1<=M<=10,000)和N,"种类"的数目1<=N<=10,000。后面的每一行将包括两个整数来描述一个"种类":第一个整数说明解决这种题目能得的分数(1<=points<=10000),第二整数说明

22、解决这种题目所需的时间(1<=minutes<=10000)。你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数来自任意的"种类"的题目数目可能任何非负数(0或更多)。计算可能得到的最大分数。PROGRAMNAME:inflateINPUTFORMAT第1行:M,N-竞赛的时间和题目"种类"的数目。第2-N+1行:两个整数:每个"种类"题目的分数和耗时。SAMPLEINPUT(fileinflate.in)3004100602501201201003520OUTPUT

23、FORMAT单独的一行包括那个在给定的限制里可能得到的最大的分数。SAMPLEOUTPUT(fileinflate.out)605从第2个"种类"中选两题，第4个"种类"中选三题示例程序如下：#include<fstream.h>ifstreamfin("inflate.in");ofstreamfout("inflate.out");constshortmaxm=10010;longbestmaxm,m,n;voidmain()shorti,j,len,pts;fin>>m>>

24、n;for(j=0;j<=m;j+)bestj=0;for(i=0;i<n;i+)fin>>pts>>len;for(j=len;j<=m;j+)if(bestj-len+pts>bestj)bestj=bestj-len+pts;fout<<bestm<<endl;/由于数组元素不减，末元素最大USACO3.3AGame题目如下：有如下一个双人游戏:N(2<=N<=100)个正整数的序列放在一个游戏平台上，两人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束。以最终得分多者

25、为胜。编一个执行最优策略的程序，最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。PROGRAMNAME:game1INPUTFORMAT第一行:正整数N,表示序列中正整数的个数。第二行至末尾:用空格分隔的N个正整数(大小为1-200)。SAMPLEINPUT(filegame1.in)6472952OUTPUTFORMAT只有一行，用空格分隔的两个整数:依次为玩家一和玩家二最终的得分。SAMPLEOUTPUT(filegame1.out)1811参考程序如下：#include<stdio.h>#defineNMAX101intbe

26、stNMAX2,tNMAX;intn;voidreadx()inti,aux;freopen("game1.in","r",stdin);scanf("%d",&n);for(i=1;i<=n;i+)scanf("%d",&aux);t=ti-1+aux;fclose(stdin);inlineintmin(intx,inty)returnx>y?y:x;voidsolve()inti,l;for(l=1;l<=n;l+)for(i=1;i+l<=n+1;i+)bestl%2

27、=ti+l-1-ti-1-min(besti+1(l-1)%2,best(l-1)%2);voidwritex()freopen("game1.out","w",stdout);printf("%d%dn",best1n%2,tn-best1n%2);fclose(stdout);intmain()readx();solve();writex();return0;USACO3.4RaucousRockers题目如下：你刚刚得到了流行的''破锣摇滚乐队录制的尚未发表的N(1<=N<=20)首歌的版权。你打算从

28、中精选一些歌曲，发行M(1<=M<=20)张CD。每一张CD最多可以容纳T(1<=T<=20)分钟的音乐，一首歌不能分装在两张CD中。不巧你是一位古典音乐迷，不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择：歌曲必须按照创作的时间顺序在CD盘上出现。选中的歌曲数目尽可能地多。PROGRAMNAME:rockersINPUTFORMAT第一行：三个整数：N,T,M.第二行：N个整数，分别表示每首歌的长度，按创作时间顺序排列。SAMPLEINPUT(filerockers.in)4524342OUTPUTFORMAT一个整数，表示可以装进M张CD盘的乐曲的最大数

29、目。SAMPLEOUTPUT(filerockers.out)3参考程序如下：#include<stdio.h>#defineMAX25intdpMAXMAXMAX,lengthMAX;intmain()FILE*in=fopen("rockers.in","r");FILE*out=fopen("rockers.out","w");inta,b,c,d,best,numsongs,cdlength,numcds;fscanf(in,"%d%d%d",&numsongs,&a

30、mp;cdlength,&numcds);for(a=1;a<=numsongs;a+)fscanf(in,"%d",&lengtha);best=0;for(a=0;a<numcds;a+)for(b=0;b<=cdlength;b+)for(c=0;c<=numsongs;c+)for(d=c+1;d<=numsongs;d+)if(b+lengthd<=cdlength)if(dpac+1>dpab+lengthdd)dpab+lengthdd=dpac+1;elseif(dpac+1>dpa+1leng

31、thdd)dpa+1lengthdd=dpac+1;if(dpac>best)best=dpac;fprintf(out,"%dn",best);return0;解决背包问题动态规划的定义：动态规划的基本思想是把待求解的问题分解成若干个子问题，先求解子问题，然后再从这些子问题的解得到原问题的解，其中用动态规划分解得到的子问题往往不是互相独立的。动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题

32、时花费时间。动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。求解步骤如下：1.找出最优解的性质，并刻画其结构特征；2. 递归地定义最优值；3. 以自底向上的方式计算出最优值；4. 根据计算最优值时得到的信息，构造最优解。问题描述及实现：背包问题：解决背包问题的方法有多种，动态规划，贪心算法，回溯法，分支定界法都能解决背包问题。其中动态规划，回溯法，分支定界法都是解决0-1背包问题的方法。背包问题与0-1背包问题的不同点在于在选择物品装入背包时，可以只选择物品的

33、一部分，而不一定是选择物品的全部。在这里，我们组用的有贪心法和动态规划法来对这个问题进行算法的分析设计。用动态规划的方法可以看出如果通过第n次选择得到的是一个最优解的话，那么第n-1次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。动态规划方法是处理分段过程最优化一类问题极其有效的方法。在实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程是如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。考虑用动态规划的方法来解决，这里的：阶段是：在前n件物品中，选取若干件物品放入背包中；状态是：在前n件物品中，选取若干件物品放入所剩空间为w的背包中的所最大价值；决策是：第n件物品放或者不放；由此可以写出动态转移方程：我们用fi,j表示在前i件物品中选择若干件放在所剩空间为j的背包里所能获得最大价值是：fi,j=maxfi-1,j-wi+pi(j>=wi),fi-1,j。这样，我们可以自底向上地得出在前m件物品中取出若干件放进背包能获得的最大价值,也就是fm,w令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值f(i,j)=maxf(i-1,j),f(i-1,j-wi)+vi,i&