动态规划-king

动态规划（DP）在分治算法中，为了解决一个大问题，我们总是将它分解成两个或更多的小问题，然后分别解决每个小问题，再把各小问题的解答组合起来就得到原来问题的借。小问题通常和原问题本质相似，只是规模小些，一般都可以用递归的方法来解决，如汉诺塔问题和快速排序都是例子。有些问题当把问题分解成子问题，使之能够从这些子问题的借得到原问题的解时，子问题的数目太多，如果把每个子问题再分解，必将得到更多的子问题，以至于最后解决问题需要耗费指数级的时间。其实，在这类问题中，子问的数目只是多项式个，于是在上述算法中，一定有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时简单查一下，这样我们可以避免大量的重复计算为了实现上述方法，我们用一个数组记录所有已解决的子问题的答案，无论子问题以后是否被用到，只要它被计算过，就将其结果存入数组中，这种方法在程序设计中被称为动态规划（DP）动态规划简介动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年，美国数学家贝尔曼（R.Bellman）提出了解决这类问题的“最优化原则”，1957年发表了他的名著《动态规划》，该书是动态规划方面的第一本著作。动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用，取得了显著的效果。动态规划简介动态规划运用于信息学竞赛是在90年代初期，它以独特的优点获得了出题者的青睐。此后，它就成为了信息学竞赛中必不可少的一个重要方法，几乎在所有的国内和国际信息学竞赛中，都至少有一道动态规划的题目。所以，掌握好动态规划，是非常重要的。动态规划简介动态规划是一种方法，是考虑问题的一种途径，而不是一种算法。因此，它不像深度优先和广度优先那样可以提供一套模式。它必须对具体问题进行具体分析。需要丰富的想象力和创造力去建立模型求解。动态规划思路：用一个数组来记录所有已解决的子问题的答案。无论子问题以后是否被用到，只要它被计算过，就将其结果存入数组中，这种方法在程序设计中被称为动态规划。相比较分治算法，提高了程序效率。最短路径问题如图表示从起点A到终点E之间各点的距离。求A到E的最短路径。以上求从A到E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径问题。记从Bi(i=1,2,3)到E的最短路径为S(Bi)，则从A到E的最短距离S(A)可以表示为：)B(S1)B(S5)B(S2min)B(SAB)B(SAB)B(SABmin)A(S321332211同样，计算S(B1)又可以归结为性质完全相同，但规模更小的问题，即分别求C1，C2，C3到E的最短路径问题S(Ci)(i=1,2,3)，而求S(Ci)又可以归结为求S(D1)和S(D2)这两个子问题。从图1.1.1可以看出，在这个问题中，S(D1)和S(D2)是已知的，它们分别是：S(D1)=5，S(D2)=2因而，可以从这两个值开始，逆向递归计算S(A)的值。计算过程如下：即S(C1)=8且如果到达C1，则下一站应到达D1；S(C2)=7且如果到达C2，则下一站应到达D2；S(C3)=12且如果到达C3，则下一站应到达D2；即S(B1)=20且如果到达B1，则下一站应到达C1；S(B2)=14且如果到达B2，则下一站应到达C1；S(B3)=19且如果到达B3，则下一站应到达C2；图的邻接矩阵如下：0251-1-1-1-1-1-1-10-1-11214-1-1-1-1-1-10-16104-1-1-1-1-1-10131211-1-1-1-1-1-1-10-1-139-1-1-1-1-1-10-165-1-1-1-1-1-1-10-110-1-1-1-1-1-1-1-10-15-1-1-1-1-1-1-1-102-1-1-1-1-1-1-1-1-10采用逆推法设f（x）表示点x到v10的最短路径长度则f(10)=0f(x)=min{f(i)+a[x，i]当a[x，i]0,xi=n}如何记录路径：１记录数字标志；２顺序或递归实现vari,j,k,m,n:longint;weight,cost:array[1..1000]oflongint;f,ff:array[0..1000,0..1000]oflongint;procedureos(i,j:longint);beginif(i=0)or(j=0)thenexit;caseff[i,j]of1:os(i-1,j);2:beginos(i-1,j-weight[i]);write(i,'');end;end;end;beginassign(input,'bag01.in');reset(input);//bag012.outassign(output,'bag01.out');rewrite(output);readln(m,n);fori:=1tondoread(weight[i]);readln;fori:=1tondoread(cost[i]);readln;fillchar(f,sizeof(f),0);fori:=1tomdof[0,i]:=0;fori:=1tondof[i,0]:=0;fori:=1tondoforj:=mdownto1dobeginifj-weight[i]=0thenbeginiff[i-1,j]f[i-1,j-weight[i]]+cost[i]thenbeginf[i,j]:=f[i-1,j];ff[i,j]:=1;endelsebeginf[i,j]:=f[i-1,j-weight[i]]+cost[i];ff[i,j]:=2;endendelsebeginf[i,j]:=f[i-1,j];ff[i,j]:=1;endend;writeln(f[n,m]);os(n,m);close(input);close(output);end.k:=0;fori:=ndownto1doforj:=1tomdoif(ff[i,j]=1)and(f[i,j]=max)thenbegininc(k);p[k]:=i;max:=max-c[i];break;end;fori:=kdownto2dowrite(p[i],'');write(p[1]);数字三角形（IOI’94）如下所示一个数字三角形738810274445265写一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字和最大每一步可沿直向下或右斜线向下走1三角形行数=100三角形中的数字为整数0，1，，，99数字三角形（IOI’94）输入：第一行为一个自然数，表示数字三角形的行数n，接下来的n行表示一个数字三角形输出：一行一个整数表示最大和5738810274445265输出：30分析假设从顶至数字三角形的某一位置的所有路径中，所经过的数字总和最大的那条路径我们称之为该位置的最大路径，由于问题规定每一步只能沿直线或右斜线向下走，若要走过某一位置，则其前一位置必为其正上方或左上方两个位置之一。由此可知，当前位置的最优路径必定与其左上方或正上方两个位置的最优路径有关，且来自其中最优的一个我们用一个两维数组a记录三角形中的数a[I,j]表示数字三角形的第I行第j列的数，再用一个两维数组maxsum记录每个位置的最优路径的数字和。计算maxsum数组可以用逐行递推的方法实现（像杨辉三角）分析按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段……第1阶段(起始点)各决策点至第n行的最佳路径。设：f[i,j]为从第i阶段中的点j至第n行的最大的数字和；则:f[n,j]=a[n,j]1=j=nf[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]}1=j=i.f[1,1]即为所求。动态规划的基本思想最优子结构用动态程序设计方法来解决一个问题的第一步是规划一个最优解的结构。我们说一个问题具有最优子结构性质，如果该问题的最优解中包含了一个或多个子问题的最优解，当一个问题呈现出最优子结构时，动态程序设计可能就是一个合适的候选方法了。动态规划的基本思想如数字三角形就有最优子结构当前位置的最优路径必定与其左上方或正上方的两个位置的最优路径有关，且来自其中最优的一个，即问题的最优解包含了其中一个子问题的最优解如果将问题稍微改变：将三角形中的数字改为-100~100之间的整数，计算从顶至底的某处的一条路径，使路径经过的数字综合最接近零，这个问题就不具备最优子结构性质，因为子问题最优反而可能造成问题的解原离零动态规划的基本思想重叠子问题子问题的空间要较小，也就是用来解原问题的一个递归算法可反复解同样的子问题，而不是总是产生新的子问题，即子问题的总数是问题规模的一个多项式。当一个递归算法不断地遇到同一问题时，我们说该最优化问题包含有重叠子问题相反地，使用分治法解决的问题往往在递归的每一步都产生出全新的问题来，如快速排序算法。动态总是充分使用重叠子问题，对每个子问题只解一次，把解放在一个数组中，需要时查看。动态规划的基本思想无后效性“过去的历史只能通过当前状态去影响它未来的发展，当前的状态是对以往历史的一个总结”，这种特性称为无后效性，是多阶段决策最优化问题的特征。想要掌握好动态规划，首先要明白几个概念：阶段、状态、决策、策略、指标函数。1．阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量。2．状态：状态表示每个阶段开始所处的自然状况和客观条件，它描述了研究问题过程中的状况，又称不可控因素。3．决策：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策，在最优控制中也称为控制。描述决策的变量，称为决策变量。4．策略：由所有阶段的决策组成的决策函数序列称为全过程策略，简称策略。5．状态转移方程：状态转移方程是确定过程由一个状态到另一个状态的演变过程。6．指标函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数。指标函数的最优值，称为最优值函数。动态规划算法的基本步骤如果碰到一个问题，能够满足以上两个条件的话，那么就可以去进一步考虑如何去设计使用动态规划：（1）划分阶段。把一个问题划分成为许多阶段来思考（2）设计合适的状态变量(用以递推的角度)（3）建立状态转移方程(递推公式)（4）寻找边界条件(已知的起始条件)如果以上几个步骤都成功完成的话，我们就可以进行编程了。最长不下降子序列设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)a(j)(ij)例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3…ie且有a(i1)a(i2)…a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。算法分析根据动态规划的原理，由后往前进行搜索。1·对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；2·若从a(n-1)开始查找，则存在下面的两种可能性：①若a(n-1)a(n)则存在长度为2的不下降序列a(n-1)，a(n)。②若a(n-1)a(n)则存在长度为1的不下降序列a(n-1)或a(n)。3·一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列