文档介绍：动态规划基本原理 1机器分配(HNOI’95) 3最长不下降序列(HNOI’97) 4凸多边形三角划分(HNOI’97) 6系统可靠性(HNOI’98) 8快餐问题(HNOI’99) 9求函数最大值(CTSC'95) 14石子合并(NOI’95) 15游览街区(NOI’97) 17积木游戏(NOI’97) 20免费馅饼(NOI’98) 24棋盘分割(NOI’99) 27钉子和小球(NOI’99) 30Subset(NOI’99) 33陨石的秘密(NOI’2001) 38商店购物(IOI’95) 42最长前缀(IOI’96) 48多边形(IOI’98) 52花店橱窗布置(IOI’99) 56选课(CTSC’98) 59拯救大兵瑞恩(CTSC’99) 63补丁VS错误(CSTS’99) 69迷宫改造(WC’99) 72奶牛浴场(WC’2002) 80HPC(WC’2001) 85交叉匹配(WC’2001练****题) 90Codes(IOI‘99) 93快乐的蜜月(CTSC2000) 102Integer(HNOI2000) 108Bar 110序关系计数问题(福建试题) 113Chain 116Land(IOI’99) 119理想收入 125动态规划基本原理近年来,涉及动态规划的各种竞赛题越来越多,每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决;而竞赛对选手运用动态规划知识的要求也越来越高,已经不再停留于简单的递推和建模上了。要了解动态规划的概念,首先要知道什么是多阶段决策问题。一、多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题。各个阶段的决策构成一个决策序列,称为一个策略。每一个阶段都有若干个决策可供选择,因而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,这个效果可以用数量来确定。策略不同,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,-1带权有向多段图让我们先来看下面的例子:如图所示的是一个带权有向的多段图,要求从A到D的最短路径的长度(下面简称最短距离)。我们可以搜索,枚举图中的每条路径,但当图的规模大起来时,搜索的效率显然不可能尽人意。让我们来试用动态规划的思路分析这道题:从图中可以看到,A点要到达D点必然要经过B1和B2中的一个,所以A到D的最短距离必然等于B1到D的最短距离加上5,或是B2到D的最短距离加上2。同样的,B1到D的最短距离必然等于C1到D的最短距离加上3或是C2到D的最短距离加上2,……。我们设G[i]为点i到点D的距离,显然G[C1]=4,G[C2]=3,G[C3]=5,根据上面的分析,有:G[B1]=min{G[C1]+3,G[C2]+2}=5,G[B2]=min{G[C2]+7,G[C3]+4}=9,再就有G[A]=min{G[B1]+5,G[B2]+2}=10,所以A到D的最短距离是10,最短路径是AàB1àC2àD。二、,以便于求解,过程不同,。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的。在前面的例子中,第一个阶段就是点A,而第二个阶段就是点A到点B,第三个阶段是点B到点C,而第四个阶段是点C到点D。,它不以人们的主观意志为转移,也称为不可控因素。在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶段某支路的终点。在前面的例子中,第一个阶段有一个状态即A,而第二个阶段有两个状态B1和B2,第三个阶段是三个状态C1,C2和C3,而第四个阶段又是一个状态D。过程的状态通常可以用一个或一组数来描述,称为状态变量。一般,状态是离散的,但有时为了方便也将状态取成连续的。当然,在现实生活中,由于变量形式的限制,所有的状态都是离散的,但从分析的观点,有时将状态作为连续的处理将会有很大的好处。此外,状态可以有多个分量(多维情形),因而用向量来代表;而且在每个阶段的状态维数可以不同。当过程按所有可能不同的方式发展时,过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了