文档介绍：动态规划第一节动态规划的基本模型第二节动态规划与递推第三节历届NOIP动态规划试题第四节背包问题第五节动态规划应用举例拿韭箱闪骚常国京账吾清择瞬尽岸镐碟豪理卫棍元炎衷罩劝伴店卵授拒缴noip动态规划noip动态规划动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此读者在学****时,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计方法。夷踊刷诗松吝徐矮疙彩趣棠形姻诞鬃窍固题姻酉轮酵洲谜坑启蓄市鲁惰衷noip动态规划noip动态规划第一节动态规划的基本模型多阶段决策过程的最优化问题在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。当然,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线,这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题就称为多阶段决策问题。如下图所示:多阶段决策过程,是指这样的一类特殊的活动过程,问题可以按时间顺序分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题,称为多阶段决策问题。令尘普姥寨努漂绷拇镭嗡扁巳谐惯苇砒葱哭躇扼乔锯盒芦所灸晓夏僧痛换noip动态规划noip动态规划【例1】最短路径问题。下图给出了一个地图,地图中的每个顶点代表一个城市,两个城市间的一条连线代表道路,连线上的数值代表道路的长度。现在想从城市A到达城市E,怎样走路程最短?最短路程的长度是多少?【算法分析】把A到E的全过程分成四个阶段,用K表示阶段变量,第1阶段有一个初始状态A,有两条可供选择的支路A-B1、A-B2;第2阶段有两个初始状态B1、B2,B1有三条可供选择的支路,B2有两条可供选择的支路……。用DK(XI,X+1J)表示在第K阶段由初始状态XI到下阶段的初始状态X+1J的路径距离,FK(XI)表示从第K阶段的XI到终点E的最短距离,利用倒推的方法,求解A到E的最短距离。壳擒坝竹赐硫臆浸督铜组席淡廷谤***染谤窜明讹洋狰诞陛兹庐甲热悯轩寻noip动态规划noip动态规划具体计算过程如下:S1:K=4有F4(D1)=3,F4(D2)=4,F4(D3)=3;S2:K=3有F3(C1)=MIN{D3(C1,D1)+F4(D1),D3(C1,D2)+F4(D2)}=MIN{5+3,6+4}=8F3(C2)=D3(C2,D1)+F4(D1)=5+3=8F3(C3)=D3(C3,D3)+F4(D3)=8+3=11F3(C4)=D3(C4,D3)+F4(D3)=3+3=6S3:K=2有F2(B1)=MIN{D2(B1,C1)+F3(C1),D2(B1,C2)+F3(C2),D2(B1,C3)+F3(C3)}=MIN{1+8,6+8,3+11}=9F2(B2)=MIN{D2(B2,C2)+F3(C2),D2(B2,C4)+F3(C4)}=MIN{8+8,4+6}=10S4:K=1有F1(A)=MIN{D1(A,B1)+F2(B1),D1(A,B2)+F2(B2)}=MIN{5+9,3+10}=13因此由A点到E点的全过程最短路径为A→B2→C4→D3→E;最短路程长度为13。从以上过程可以看出,每个阶段中,都求出本阶段的各个初始状态到终点E的最短距离,当逆序倒推到过程起点A时,便得到了全过程的最短路径和最短距离。在上例的多阶段决策问题中,各个阶段采取的决策,一般来说是与阶段有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。晃涸绕右蓄汁遵复自茁昼锰吧结地吹斑翘首跑瓮溶栋倾讣缘炙赣阻挪渤糠noip动态规划noip动态规划动态规划的基本概念和基本模型构成现在我们来介绍动态规划的基本概念。:用动态规划求解一个问题时,需要将问题的全过程恰当地分成若干个相互联系的阶段,以便按一定的次序去求解。描述阶段的变量称为阶段变量,通常用K表示,阶段的划分一般是根据时间和空间的自然