第七章动态规划
规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。
动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。
动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。
§7.1 动态规划的基本理论
1.1多阶段决策过程的数学描述
有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。
由于每一阶段都有一个决策，所以每一阶段都应存在一个衡量决策效益大小的指标函数，这一指标函数称为阶段指标函数，用g n 表示。显然g n 是状态变量S n 和决策变量d n 的函数，即g n = r （S n ，d n ），如图7-1（b ）所示。显然，输出是输入和决策的函数，即：
),(1n n n d S f S =+ （7-1）
式（7-1）即为状态转移律。在由N 个阶段构成的过程里，前一个阶段的输出即为后一个阶段的输入。
1.2 动态规划的基本概念
动态规划的数学描述离不开它的一些基本概念与符号，因此有必要在介绍多阶段决策过程的数学描述的基础上，系统地介绍动态规划的一些基本概念。
1． 阶段（stage ）
阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k 来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。对于具有N 个阶段的决策过程，其阶段变量k ＝1，2，…，N 。 2． 状态（state ）
状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态既反映前面各阶段系列决策的结局，又是本阶段决策的一个出发点和依据；它是各阶段信息的传递点和结合点。各阶段的状态通常用状态变量S k 来加以描述。作为状态应具有这样的性质：如果某阶段状态给定后，则该阶段以后过程的发展不受此阶段以前各阶段状态的影响。换句话说，过程的历史只能通过当前的状态来影响未来，当前的状态是以往历史的一个总结。这个性质称为无后效性（the future is independent of the past ）或健忘性（the process is forgetful ）。
3． 决策（decision ）
决策是指决策者在所面临的若干个方案中做出的选择。决策变量d k 表示第k 阶段的决策。决策变量d k 的取值会受到状态S k 的某种限制，用D k （S k ）表示第k 阶段状态为S k 时决策变量允许的取值范围，称为允许决策集合，因而有d k （S k ）∈D k （S k ）。
4． 状态转移律（transformation function ）
状态转移律是确定由一个状态到另一状态演变过程的方程，这种演变的对应关系记为S k+1 = T k （S k , d k ）。
5． 策略（policy ）与子策略（sub-policy ）
由所有阶段决策所组成的一个决策序列称为一个策略，具有N 个阶段的动态规划问题的策略可表示为：
)}(,),(),({2211N N S d S d S d Λ
从某一阶段开始到过程终点为止的一个决策子序列，称为过程子策略或子策略。从第k 个阶段起的一个子策略可表示为：
)}(,),(),({11N N k k k k S d S d S d Λ++
6． 指标函数
指标函数有阶段指标函数和过程指标函数之分。阶段指标函数是对应某一阶段决策的效率度量，用g k = r （S k ，d k ）来表示；过程指标函数是用来衡量所实现过程优劣的数量指标，是定义在全过程（策略）或后续子过程（子策略）上的一个数量函数，从第k 个阶段起的一个子策略所对应的过程指标函数常用G k,N 来表示，即：
),,,,,,(11,N N k k k k N k d S d S d S R G Λ++=
构成动态规划的过程指标函数，应具有可分性并满足递推关系；即：
N k k N k G g G ,1,+⊕=
这里的⊕表示某种运算，最常见的运算关系有如下二种：
（1） 过程指标函数是其所包含的各阶段指标函数的“和”，即：
∑==N
k
j j N k g G ,
于是
N k k N k G g G ,1,++=
（2） 过程指标函数是其所包含的各阶段指标函数的“积”，即：
∏==N
k
j j N k g G ,
于是
N k k N k G g G ,1,+?=
7． 最优指标函数
从第k 个阶段起的最优子策略所对应的过程指标函数称为最优指标函数，可以用式（7-2）加以表示：
}{)(1~N k k d k k g g g opt S f N
k ⊕⊕⊕=+Λ （7-2）
其中“opt ”是最优化“optimization ”的缩写，可根据题意取最大“max ”或最小“min ”。在不同的问题中，指标函数的含义可能是不同的，它可能是距离、利润、成本、产量或资源量等。
1.3 动态规划的数学模型
动态规划的数学模型除包括式（7-2）外，还包括阶段的划分、各阶段的状态变量和决策变量的选取、允许决策集合和状态转移律的确定等。
如何获得最优指标函数呢？一个N 阶段的决策过程，具有如下一些特性： （1） 刚好有N 个决策点；
（2） 对阶段k 而言，除了其所处的状态k S 和所选择的决策k d 外，再没有任何其它
因素影响决策的最优性了；
（3） 阶段k 仅影响阶段1+k 的决策，这一影响是通过1+k S 来实现的；
（4） 贝尔曼（Bellman ）最优化原理：在最优策略的任意一阶段上，无论过去的状态
和决策如何，对过去决策所形成的当前状态而言，余下的诸决策必须构成最优子策略。
根据贝尔曼（Bellman ）最优化原理，可以将式（7-2）表示为递推最优指标函数关系式（7-3）或式（7-4）：
)}({}{)(111~++++=⊕⊕⊕=k k k d N k k d k k S f g opt g g g opt S f k
N
k Λ （7-3）
)}({}{)(111~+++?=⊕⊕⊕=k k k d N k k d k k S f g opt g g g opt S f k
N
k Λ （7-4）
利用式（7-3）和式（7-4）可表示出最后一个阶段（第N 个阶段，即k=N ）的最优指标函数：
)}({)(11+++=N N N d N N S f g opt S f N
（7-5）
)}({)(11++?=N N N d N N S f g opt S f N
（7-6）
其中)(11++N N S f 称为边界条件。一般情况下，第N 阶段的输出状态1+N S 已经不再影响本过程的策略，即式（7-5）中的边界条件0)(11=++N N S f ，式（7-6）中的边界条件1)(11=++N N S f ；但当问题第N 阶段的输出状态1+N S 对本过程的策略产生某种影响时，边界条件)(11++N N S f 就要根据问题的具体情况取适当的值，这一情况将在后续例题中加以反映。
已知边界条件)(11++N N S f ，利用式（7-3）或式（7-4）即可求得最后一个阶段的最优指标函数)(N N S f ；有了)(N N S f ，继续利用式（7-3）或式（7-4）即可求得最后两个阶段的最优指标函数)(11--N N S f ；有了)(11--N N S f ，进一步又可以求得最后三个阶段的最优指标函数)(22--N N S f ；反复递推下去，最终即可求得全过程N 个阶段的最优指标函数)(11S f ，从而使问题得到解决。由于上述最优指标函数的构建是按阶段的逆序从后向前进行的，所以也称为动态规划的逆序算法。
通过上述分析可以看出，任何一个多阶段决策过程的最优化问题，都可以用非线性规划（特殊的可以用线性规划）模型来描述；因此，从原则上讲，一般也可以用非线性规划（或线性规划）的方法来求解。那么利用动态规划求解多阶段决策过程有什么优越性、又有什么局限性呢？
动态规划的优点：第一，求解更容易、效率更高。动态规划方法是一种逐步改善法，它把原问题化成一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少得多，约束集合也简单得多，故较易于确定最优解。第二，解的信息更丰富。非线性规划（或线性规划）的方法是对问题的整体进行一次性求解的，因此只能得到全过程的解；而动态规划方
法是将过程分解成多个阶段进行求解的，因此不仅可以得到全过程的解，同时还可以得到所有子过程的解。
动态规划的缺点：第一，没有一个统一的标准模型。由于实际问题不同，其动态规划模型也就各有差异，模型构建存在一定困难。第二，应用条件苛刻。由于构造动态规划模型状态变量必须满足“无后效性”条件，这一条件不仅依赖于状态转移律，还依赖于允许决策集合和指标函数的结构，不少实际问题在取其自然特征作为状态变量时并不满足这一条件，这就降低了动态规划的通用性。第三，状态变量存在“维数障碍”。最优指标函数)(k k S f 是状态变量的函数，当状态变量的维数增加时，最优指标函数的计算量将成指数倍增长；因此，无论是手工计算还是电算“维数障碍”都是无法完全克服的。
§7.2 确定性动态规划问题
确定性动态规划问题即阶段的输出状态完全由其输入状态和决策所决定的动态规划问题。确定性动态规划解决的问题可能包含经济管理的方方面面，可以是最短路线问题，可以是资源配置问题，也可以是其他的规划优化问题。最短路线问题直观、具体地演示了动态规划的基本概念和基本步骤；因此，让我们首先来分析一下最短路线问题。
2-1最短路线问题
[例7-1] 美国黑金石油公司（The Black Gold Petroleum Company ）最近在阿拉斯加（Alaska ）的北斯洛波（North Slope ）发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站（结点C ）与装运港（结点P 1、P 2、P 3）之间需要若干个中间站，中间站之间的联通情况如图7-2所示，图中线段上的数字代表两站之间的距离（单位：10千米）。试确定一最佳的输运线路，使原油的输送距离最短。
解：最短路线有一个重要性质，即如果由起点A 经过B 点和C 点到达终点D 是一条最短路线，则由B 点经C 点到达终点D 一定是B 到D 的最短路（贝尔曼最优化原理）。此性质用反证法很容易证明，因为如果不是这样，则从B 点到D 点有另一条距离更短的路线存在，不妨假设为B —P —D ；从而可知路线A —B —P —D 比原路线A —B —C —D 距离短，这与原路线A —B —C —D 是最短路线相矛盾，性质得证。
根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法，将此过程划分为4个阶段，即阶段变量4,3,2,1 k ；取过程在各阶段所处的位置为状态变量k S ，按逆序算法求解。
当4=k 时：
由结点M 31到达目的地有两条路线可以选择，即选择P 1或P 2；故：
668min )(3144=?
??
???==M S f 选择P 2
由结点M 32到达目的地有三条路线可以选择，即选择P 1、P 2或P 3；故：
3734min )(3244=??
?
???????==M S f 选择P 2
由结点M 33到达目的地也有三条路线可以选择，即选择P 1、P 2或P 3；故：
5567min )(3344=??
?
???????==M S f 选择P 3
由结点M 34到达目的地有两条路线可以选择，即选择P 2或P 3；故：
343min )(3444=?
??
???==M S f 选择P 2
当3=k 时：
由结点M 21到达下一阶段有三条路线可以选择，即选择M 31、M 32或M 33；故：
105637610min )(2133=??
?
???????+++==M S f 选择M 32
由结点M 22到达下一阶段也有三条路线可以选择，即选择M 31、M 32或M 33；故：
10553769min )(2233=??
?
???????+++==M S f 选择M 32或M 33
由结点M 23到达下一阶段也有三条路线可以选择，即选择M 32、M 33或M 34；故：
93654311min )(2333=??
?
???????+++==M S f 选择M 33或M 34
当2=k 时：
由结点M 11到达下一阶段有两条路线可以选择，即选择M 21或M 22；故：
16106108min )(1122=?
??
???++==M S f 选择M 22
由结点M 12到达下一阶段也有两条路线可以选择，即选择M 22或M 23；故：
19911109min )(1222=?
??
???++==M S f 选择M 22
当1=k 时：
由结点C 到达下一阶段有两条路线可以选择，即选择M 11或M 12；故：
2819101612min )(11=?
??
???++==C S f 选择M 11
从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路：C —
M 11—M 22—M 32—P 2；C —M 11—M 22—M 33—P 3。最短的输送距离是280千米。
2-2资源分配问题 所谓资源分配问题，就是将一定数量的一种或若干种资源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以使资源得到最有效地利用。设有m 种资源，总量分别为b i （i = 1,2,?,m ），用于生产n 种产品，若用x ij 代表用于生产第j 种产品的第i 种资源的数量（j = 1,2,?,n ），则生产第j 种产品的收益是其所获得的各种资源数量的函数，即g j = f （x 1j ,x 2j ,?, x mj ）。由于总收益是n 种产品收益的和，此问题可用如下静态模型加以描述：
∑==n
j j g z 1
max
i n
j ij
b x
=∑=1
),,2,1(m i Λ=
0≥ij x ),,2,1;,,2,1(n j m i ΛΛ==
若x ij 是连续变量，当g j = f （x 1j ,x 2j ,?, x mj ）是线性函数时，该模型是线性规划模型；当g j = f （x 1j ,x 2j ,?, x mj ）是非线性函数时，该模型是非线性规划模型。若x ij 是离散变量或（和）g j = f （x 1j ,x 2j ,?, x mj ）是离散函数时，此模型用线性规划或非线性规划来求解都将是非常麻烦的。然而在此情况下，由于这类问题的特殊结构，可以将它看成为一个多阶段决策问题，并利用动态规划的递推关系来求解。
本教材只考虑一维资源的分配问题，设状态变量S k 表示分配于从第k 个阶段至过程最终（第N 个阶段）的资源数量，即第k 个阶段初资源的拥有量；决策变量x k 表示第k 个阶段资源的分配量。于是有状态转移律：
k k k x S S -=+1
允许决策集合：
}0|{)(k k k k k S x x S D ≤≤=
最优指标函数（动态规划的逆序递推关系式）：
)}()({max )(11
0++≤≤+=k k k k S x k k S f x g S f k
k )1,,2,1,(Λ--=N N N k
0)(11=++N N S f
利用这一递推关系式，最后求得的)(11S f 即为所求问题的最大总收益，下面来看一个具体的例子。
[例7-2] 某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表7-1所示。试确定500万元资本的分配方案，以使公司总的年利润增长额最大。
解：将问题按工厂分为三个阶段3,2,1=k ，设状态变量k S （3,2,1=k ）代表从第k 个工厂到第3个工厂的投资额，决策变量k x 代表第k 个工厂的投资额。于是有状态转移率
k k k x S S -=+1、允许决策集合}0|{)(k k k k k S x x S D ≤≤=和递推关系式：
)}()({max )(1
0k k k k k S x k k x S f x g S f k
k -+=+≤≤ )1,2,3(=k
0)(44=S f
当3=k 时：
)}({max }0)({max )(330330333
33
3x g x g S f S x S x ≤≤≤≤=+=
于是有表7-2，表中*
3x 表示第三个阶段的最优决策。
单位：百万元
当2=k 时：
)}()({max )(223220222
2x S f x g S f S x -+=≤≤
于是有表7-3。
单位：百万元
当时：
)}()({max )(112110111
1x S f x g S f S x -+=≤≤
于是有表7-4。
然后按计算表格的顺序反推算，可知最优分配方案有两个：（1）甲工厂投资200万元，
乙工厂投资200万元，丙工厂投资100万元；（2）甲工厂没有投资，乙工厂投资200万元，丙工厂投资300万元。按最优分配方案分配投资（资源），年利润将增长210万元。
这个例于是决策变量取离散值的一类分配问题，在实际问题中，相类似的问题还有销售店的布局（分配）问题、设备或人力资源的分配问题等。在资源分配问题中，还有一种决策变量为连续变量的资源分配问题，请见例7-3。
[例7-3] 机器负荷分配问题。某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量（件）函数为x g 81=，其中x 为投入高负荷生产的机器数量，年度完好率7.0=α（年底的完好设备数等于年初完好设备数的70%）；在低负荷下生产的产量（件）函数为y g 52=，其中y 为投入低负荷生产的机器数量，年度完好率9.0=β。假定开始生产时完好的机器数量为1000台，试问每年应如何安排机器在高、低负荷下的生产，才能使5年生产的产品总量最多？
解：设阶段k 表示年度（5,4,3,2,1=k ）；状态变量k S 为第k 年度初拥有的完好机器数量（同时也是第1-k 年度末时的完好机器数量）。决策变量k x 为第k 年度分配高负荷下生产的机器数量，于是k k x S -为该年度分配在低负荷下生产的机器数量。这里的k S 和k x 均为连续变量，它们的非整数值可以这样理解：如6.0=k S 就表示一台机器在第k 年度中正常工作时间只占全部时间的60%；3.0=k x 就表示一台机器在第k 年度中只有30%的工作时间在高负荷下运转。状态转移方程为：
k k k k k k k k k x S x S x x S x S 2.09.0)(9.07.0)(1-=-+=-+=+βα
允许决策集合：
}0|{)(k k k k k S x x S D ≤≤=
设阶段指标),(k k k x S Q 为第k 年度的产量，则：
k k k k k k k k x S x S x x S Q 35)(58),(+=-+=
过程指标是阶段指标的和，即：
∑==5
5~k
j j k Q Q
令最优值函数)(k k S f 表示从资源量k S 出发，采取最优子策略所生产的产品总量，因而有逆推关系式：
)}2.09.0(35{max )(1)
(k k k k k S D x k k x S f x S S f k k k -++=+∈
边界条件0)(66=S f 。
当5=k 时：
}35{max )}(35{max )(55066550555
55
5x S S f x S S f S x S x +=++=≤≤≤≤
因)(55S f 是关于5x 的单调递增函数，故取55S x =*
，相应有5558)(S S f =。
当4=k 时：
)}2.09.0(35{max )(445440444
4x S f x S S f S x -++=≤≤
)}2.09.0(835{max 444404
4x S x S S x -++=≤≤
}4.12.12{max 4404
4x S S x +=≤≤
因)(44S f 是关于4x 的单调递增函数，故取44S x =*
，相应有4446.13)(S S f =；依次类推，可求得：
当3=k 时：33S x =*
，3335.17)(S S f =
当2=k 时：02=*
x ，2228.20)(S S f =
当1=k 时：01=*
x ，237007.23)1000(111===S S f
计算结果表明最优策略为：01=*x ，02=*x ，33S x =*，44S x =*
，55S x =*；即前两
年将全部设备都投入低负荷生产，后三年将全部设备都投入高负荷生产，这样可以使5年的总产量最大，最大产量是23700件。
有了上述最优策略，各阶段的状态也就随之确定了，即按阶段顺序计算出各年年初的完好设备数量。
10001=S
90002.010009.02.09.0112=?-?=-=x S S 81002.09009.02.09.0223=?-?=-=x S S 5678102.08109.02.09.0334=?-?=-=x S S 3975672.05679.02.09.0445=?-?=-=x S S 2783972.03979.02.09.0556=?-?=-=x S S
上面所讨论的过程始端状态1S 是固定的，而终端状态6S 是自由的，实现的目标函数是5年的总产量最高。如果在终端也附加上一定的约束条件，如规定在第5年结束时，完好的机器数量不低于350台（上面的例子只有278台），问应如何安排生产，才能在满足这一终端要求的情况下使产量最高呢？
解：阶段k 表示年度（5,4,3,2,1=k ）；状态变量k S 为第k 年度初拥有的完好机器数量；决策变量k x 为第k 年度分配高负荷下生产的机器数量；状态转移方程为：
k k k k k k k k k x S x S x x S x S 2.09.0)(9.07.0)(1-=-+=-+=+βα
终端约束：
3506≥S 3502.09.055≥-x S 17505.455-≤S x
允许决策集合：}0|{)(k k k k k S x x S D ≤≤=“加”第k 阶段的终端递推条件
对于5=k ，考虑终端递推条件有：
}17505.40|{)(555555S S x x S D ≤-≤≤=
3895005≥≥S
同理其他各阶段的允许决策集合可在过程指标函数的递推中产生。 设阶段指标：
k k k k k k k k x S x S x x S Q 35)(58),(+=-+=
过程指标：
∑==5
5~k
j j k Q Q
最优值函数：
)}2.09.0(35{max )(1)
(k k k k k S D x k k x S f x S S f k k k -++=+∈
边界条件0)(66=S f 。 当5=k 时：
}35{max )}(35{max )(55)
(6655)
(55555555x S S f x S S f S D x S D x +=++=∈∈
因)(55S f 是关于5x 的单调递增函数，故取17505.455-=*
S x ，相应有：
5517505.40S S ≤-≤
即： 5003895≤≤S
17505.455-=*S x ，52505.18)(555-=S S f
当4=k 时：
)}2.09.0(35{max )(44544)
(44444x S f x S S f S D x -++=∈
}52507.065.21{max 44)
(444--=∈x S S D x
由5002.09.0445≤-=x S S 可得25005.444-≥S x ，又因)(44S f 是关于4x 的单调递减函数，故取25005.444-=*
S x ，相应有：
4425005.40S S ≤-≤ 7145564≤≤S
25005.444-=*S x ，35005.18)(444-=S S f
当3=k 时：
)}2.09.0(35{max )(33433)
(33333x S f x S S f S D x -++=∈
}35007.065.21{max 33)
(333--=∈x S S D x
由7142.09.0334≤-=x S S 可得35705.433-≥S x ，又因)(33S f 是关于3x 的单调递
减函数，故取35705.433-=*
S x ，相应有：
3335705.40S S ≤-≤ 10207933≤≤S
由于10001=S ，所以10203≤S 是恒成立的，即7933≥S 。
35705.433-=*S x ，10015.18)(333-=S S f
当2=k 时：
)}2.09.0(35{max )(22322)
(22222x S f x S S f S D x -++=∈
}10017.065.21{max 22)
(222--=∈x S S D x
因)(22S f 是关于2x 的单调递减函数，而3S 的取值并不对2x 有下界的约束，故取
02=*
x ，相应有：
02=*
x ，100165.21)(222-=S S f
当1=k 时：
)}2.09.0(35{max )(11211)
(11111x S f x S S f S D x -++=∈
}100133.1485.24{max 11)
(111--=∈x S S D x
因)(11S f 是关于1x 的单调递减函数，故取01=*
x ，相应有：
01=*x ，234841001485.24)1000(111=-==S S f
计算结果表明最优策略为：
（1）第1年将全部设备都投入低负荷生产。
10001=S ，01=x ，90002.010009.02.09.0112=?-?=-=x S S
5000031000535),(11111=?+?=+=x S x S Q
（2）第2年将全部设备都投入低负荷生产。
9002=S ，02=x ，81002.09009.02.09.0223=?-?=-=x S S
450003900535),(22222=?+?=+=x S x S Q
（3）第3年将7535708105.435705.433=-?=-=*
S x 台完好设备投入高负荷生产，将剩余的7357581033=-=-*
x S 台完好设备投入低负荷生产。
4275753810535),(33333=?+?=+=x S x S Q 714752.08109.02.09.0334=?-?=-=x S S
（4）第4年将71325007145.425005.444=-?=-=*
S x 台完好设备均投入高负荷生产，将剩余的1台完好设备均投入低负荷生产。
57097133714535),(44444=?+?=+=x S x S Q 5007132.07149.02.09.0445=?-?=-=x S S
（5）第5年将50017505005.417505.455=-?=-=*
S x ，即将5005=S 台完好设
备均投入高负荷生产。
40005003500535),(55555=?+?=+=x S x S Q 3505002.05009.02.09.0556=?-?=-=x S S
23484),()1000(5
1
11===∑=j j j j x S Q S f
2-3存贮控制问题
由于供给与需求在时间上存在差异，需要在供给与需求之间构建存贮环节以平衡这种差异。存贮物资需要付出资本占用费和保管费等，过多的物资储备意味着浪费；而过少的储备又会影响需求造成缺货损失。存贮控制问题就是要在平衡双方的矛盾中，寻找最佳的采购
批量和存贮量，以期达到最佳的经济效果。
[例7-4] 某鞋店销售一种雪地防潮鞋，以往的销售经历表明，此种鞋的销售季节是从10月1日至3月31日。下个销售季节各月的需求预测值如表7-5所示。
表7-5 (单位：双)
该鞋店的此种鞋完全从外部生产商进货，进货价每双4美元。进货批量的基本单位是箱，每箱10双。由于存贮空间的限制，每次进货不超过5箱。对应不同的订货批量，进价享受一定的数量折扣，具体数值如表7-6所示。
表7-6
假设需求是按一定速度均匀发生的，订货不需时间，但订货只能在月初办理一次，每次订货的采购费（与采购数量无关）为10美元。月存贮费按每月月底鞋的存量计，每双0.2美元。由于订货不需时间，所以销售季节外的其他月份的存贮量为“0”。试确定最佳的进货方案，以使总的销售费用最小。
解：阶段：将销售季节6个月中的每一个月作为一个阶段，即6,,2,1Λ=k ；
状态变量：第k 阶段的状态变量k S 代表第k 个月初鞋的存量； 决策变量：决策变量k x 代表第k 个月的采购批量；
状态转移律：k k k k d x S S -+=+1（k d 是第k 个月的需求量）； 边界条件：071==S S ，0)(77=S f ；
阶段指标函数：),(k k k x S r 代表第k 个月所发生的全部费用，即与采购数量无关的采购费k C 、与采购数量成正比的购置费k G 和存贮费k Z 。其中：
,100
,0{
>==k k k x x C ；k x k x p G ?=；)(2.0k k k k d x S Z -+= 最优指标函数：最优指标函数具有如下递推形式
)({min )(11+++++=k k k k k x k k S f Z G C S f k
)}()(2.0{min 1k k k k k k k k k x d x S f d x S G C k
-++-+++=+
当6=k 时（3月）：
表7-7
当5=k 时（2月）：
当4=k 时（1月）：
当3=k 时（12月）：
表7-10
当2=k 时（11月）：
当1=k 时（10月）：
表7-12
利用状态转移律，按上述计算的逆序可推算出最优策略：10月份采购4箱（40双），
11月份采购5箱（50双），12月份不采购，1月份采购4箱（40双），2月份采购5箱（50双），3月份不采购；最小的销售费用为606美元。
2-4用动态规划求解非线性规划问题
非线性规划问题的求解（在第六章中已讨论）是非常困难的；然而，对于有些非线性规划问题，如果转化为用动态规划来求解将是十分方便的。
[例7-5] 用动态规划求解
32
21max x x x z ??=
36
321=++x x x
0,,321≥x x x
解：阶段：将问题的变量数作为阶段，即3,2,1=k ； 决策变量：决策变量k x ；
状态变量：状态变量k S 代表第k 阶段的约束右端项，即从k x 到3x 占有的份额； 状态转移律：k k k x S S -=+1； 边界条件：361=S ，1)(44=S f ； 允许决策集合：k k S x ≤≤0 当3=k 时：
3
3
3
33
3|}{max )}({max )(330443033S x S x S x S x S f x S f =≤≤≤≤*==?=
当2=k 时：
)}({max )}({max )(2222033220222
22
2x S x S f x S f S x S x -=?=≤≤≤≤
设)(222
2x S x h -=，于是22222)(22x x S x dx dh
--= 令0)(2222222=--=x x S x dx dh ，可得02=x 或232S 又因2222226222)(2222
x S x x x S dx
h d -=---=，所以： 02|
20222
2>==S x dx h
d ，02=x 是)(22S f 的极小值点
0242|
2222
322222<-=-==S S S S x dx h
d ，2322S x =是)(22S f 的极大值点
于是：
2
322
|)(3227
4
22S x S S f =*=
当1=k 时：
})({max )}({max )(311274
102210111
11
1x S x S f x S f S x S x -?=?=≤≤≤≤
同上可得：
9464
14164
1
111
411
|2624436)36(==*=?=
==S x S S f
由27936112=-=-=*
x S S ，有18273223
22=?==
*S x
由91827223=-=-=*x S S ，有933==*
S x
于是得到最优解)9,18,9(=*
X
，最优值26244=*z 。
习题：
1． 某公司打算向它的三个营业区增设6个销售店，每个营业区至少增设1个。各营业区每
年增加的利润与增设的销售店个数有关，具体关系如表1所示。试规划各营业区应增设销售店的个数，以使公司总利润增加额最大。
2． 某工厂有100台机器，拟分4个周期使用，在每一周期有两种生产任务，据经验把机器
投入第一种生产任务，则在一个周期中将有六分之一的机器报废，投入第二种生产任务，则有十分之一的机器报废。如果投入第一种生产任务每台机器可收益1万元，投入第二种生产任务每台机器可收益0.5万元。问怎样分配机器在4个周期内的使用才能使总收益最大？
3． 某公司生产一种产品，估计该产品在未来四个月的销售量分别为300、400、350和250
件。生产该产品每批的固定费用为600元，每件的变动费用为5元，存储费用为每件每月2元。假定第一个月月初的库存为100件，第四个月月底的存货为50件。试求该公司在这四个月内的最优生产计划。
例1：机器负荷分配问题 某公司新购进1000台机床，每台机床都可在高、低两种不同的负荷下进行生产，设在高负荷下生产的产量函数为g(x )=10x （单位：百件），其中x 为投入生产的机床数量，年完好率为a =0.7；在低负荷下生产的产量函数为h(y)=6y （单位：百件），其中y 为投人生产的机床数量，年完好率为b=0.9。计划连续使用5年，试问每年如何安排机床在高、低负荷下的生产计划，使在五年内生产的产品总产量达到最高。 例2：某企业通过市场调查，估计今后四个时期市场对某种产品的需要量如下表： 时期(k) 1 2 3 4 需要量(d k ) 2（单位） 3 2 4 假定不论在任何时期，生产每批产品的固定成本费为3(千元)，若不生产，则为零；生产单位产品成本费为1(千元)；每个时期生产能力所允许的最大生产批量为不超过6个单位，则任何时期生产x 个单位产品的成本费用为： 若 0＜x ≤6 ， 则生产总成本＝3十1·x 若 x ＝0 ， 则生产总成本＝0 又设每个时期末未销售出去的产品，在一个时期内单位产品的库存费用为0.5(千元)，同时还假定第1时期开始之初和在第4个时期之末，均无产品库存。现在我们的问题是；在满足上述给定的条件下，该厂如何安排各个时期的生产与库存，使所花的总成本费用最低？ 例3：设某企业在第一年初购买一台新设备，该设备在五年内的年运行收益、年运行费用及更换新设备的净费用如下表：（单位：万元） 年份(k) 役龄(t) 运行收益()k g t 运行费用()k r t 更新费用()k c t 第一年 0 22 6 18 第二年 0 1 23 21 6 8 19 22
[1]POJ动态规划题目列表 容易： 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵，求平衡）, 1936,1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029,2039, 2063, 2081, 2082,2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353,2355, 2356, 2385, 2392, 2424, 不易： 1019,1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707,1733(区间减法加并查集), 1737, 1837, 1850, 1920(加强版汉罗塔), 1934(全部最长公共子序列), 1937(计算几何), 1964(最大矩形面积，O(n)算法), 2138, 2151, 2161(烦，没写), 2178, 推荐： 1015, 1635, 1636(挺好的), 1671, 1682, 1692(优化), 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411 状态 DP 树 DP 构造最优解四边形不等式单调队列 1015 Jury Compromise 1029 False coin 1036 Gangsters 1037 A decorative fence 1038 Bugs Integrated, Inc. 1042 Gone Fishing 1050 To the Max 1062 昂贵的聘礼 1074 Parallel Expectations 1080 Human Gene Functions 1088 滑雪 1093 Formatting Text 1112 Team Them Up! 1141 Brackets Sequence 1143 Number Game
动态规划练习题 [题1] 多米诺骨牌（DOMINO） 问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。 现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。 输入格式： 文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。 输出格式： 只有一个整数在文件的第一行。这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。 [题2] Perform巡回演出 题目描述: Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出). 由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表. 输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去. 每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束. 输出: 对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0. 样例输入: 样例输出：
动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型 多阶段决策过程的最优化问题。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么
2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配 资金，使总效益值最大？## 表8－47 解：设S－A,B,C项目的总投资额，S－B、C项目的总投资额21S－C 项目的投资额；3X－k项目的投资额；k（X－A项目的投资额，X －B项目的投资额，X－C项目的投资额）312W（S,X）－对K项目投资X后的收益：W（S,X）＝W (X) kkkkkkkkk T (S,X)－S=S-X k k+1kkkk f (S)－当K至第3项目允许的投资额为S时所能获得的最大收益。kkk为获得最大利润，必须将4百万全部投资，假设有4阶段存在，有S＝0，建立递归方程4f(S)=0 k4
f (S)=max{ W (X)+f(S)} k=3,2,1 k+1kk +1kkk X∈D(S) kkk第一步，K=3 f(S)=0 44 f (S)=max{W (X)+f (S)} 434333X∈D(S) 333S=S-X3 34 第二步：)} f (S (X (S)=max{W)+f K=2 322322) X ∈D(S 222-X =S S232 W (X)+f (S-X) 22322
第三步：)} (S (X) =max f (S {W)+ f K=1 211121) D X∈(S111- X S= S 1 21 ) (X- X)+ f (SW1 12 11 S=4 →S=1 →S=1 312↓↓ ↓ X*=3 X*=0 X*=1 312百万。1投资C 不投资B 百万，3投资A． 总收益164百万元。 3.（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。每个营业区至少设一家，所获利润如表。问设立的6家销售店数应如何分配，可使总利润最大？
动态规划 一·动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。 二·动态规划法基本概念 一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段 阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=1.2….n.表示。
1.状态 状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是可以直接或者是间接可以观测的。描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。用X(k)表示第k阶段的允许状态集合。 n 个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演变的结果。 根据演变过程的具体情况，状态变量可以是离散的或是连续的。为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散的变量视为连续的。 2．决策 当一个阶段的状态确定后，可以做出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）描述决策的变量称为决策变量（decision virable）。变量允许取值的范围称为允许决策集合（set of admissble
动态规划 装箱问题（01背包）： 有一个箱子容量为VV（正整数，0≤V≤20000），同时有n个物品（0 完全背包的模板题面是这样的：设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以无限选取)，使其重量的和小于等于M，而价值的和为最大。 完全背包 [无限量]的采摘药输入： 70 3 71 100 69 1 1 2 输出：140 每个数组在满足条件，可以遍历多次 01背包 实现代码：采药-传送门 输入： 70 3 71 100 69 1 1 2 输出：3 每个数组遍历一遍 题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1-5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 设第jj件物品的价格为v_[j]，重要度为w_[j]，共选中了k件物品，编号依次为j_1,j_2,…,j_k，则所求的总和为： w_[j_k]v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]。 第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（dynamic programming）同前面介绍过的各种优化方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。当然，由于动态规划不是一种特定的算法，因而它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。1961年贝尔曼出版了他的第二部著作，并于1962年同杜瑞佛思（Dreyfus）合作出版了第三部著作。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。许多规划问题用动态规划的方法来处理，常比线性规划或非线性规划更有效。特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。 动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。本教材主要介绍动态规划的基本概念、理论和方法，并通过典型的案例说明这些理论和方法的应用。 §7.1 动态规划的基本理论 1.1多阶段决策过程的数学描述 有这样一类活动过程，其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策，以使整个过程达到最佳的活动效果。任何一个阶段（stage，即决策点）都是由输入（input）、决策（decision）、状态转移律（transformation function）和输出（output）构成的，如图7-1（a）所示。其中输入和输出也称为状态（state），输入称为输入状态，输出称为输出状态。 动态规划练习【题目一览】 总分 【问题描述】 学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。 我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员，应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间M（1<=M<=10000）（不要担心，你要到了训练营中才会有长时间的比赛）和“种类”的数目N（1<=N<=10000）。后面的每一行将包括两个整数来描述一个“种类”： 第一个整数说明解决这种题目能得的分数（1<=points<=10000），第二整数说明解决这种题目所需的时间（1<=minutes<=10000）。你的程序应该确定我们应该从每个“种类”中选多少道题目使得能在竞赛的时间中得到最大的分数。 来自任意的“种类”的题目数目可能任何非负数（0或更多）。 计算可能得到的最大分数。 【输入格式】 输入文件中的第1行：M，N--竞赛的时间和题目“种类”的数目。 第2～N+1行：两个整数：每个“种类”题目的分数和耗时。 【输出格式】 输出文件中仅一行，包括那个在给定的限制里可能得到的最大的分数。 【输入输出样例】 输入： 300 4 100 60 250 120 120 100 35 20 输出： 605 从第2个“种类”中选两题第4个“种类”中选三题。 邮票 【问题描述】 已知一个N枚邮票的面值集合（如，{1分，3分}）和一个上限K——表示信封上能够贴K张邮票。计算从1到M的最大连续可贴出的邮资。 例如，假设有1分和3分的邮票；你最多可以贴5张邮票。很容易贴出1到5分的邮资（用1分邮票贴就行了），接下来的邮资也不难： 6 = 3 + 3 7 = 3 + 3 + 1 8 = 3 + 3 + 1 + 1 9 = 3 + 3 + 3 10 = 3 + 3 + 3 + 1 11 = 3 + 3 + 3 + 1 + 1 12 = 3 + 3 + 3 + 3 13 = 3 + 3 + 3 + 3 + 1 然而，使用5枚1分或者3分的邮票根本不可能贴出14分的邮资。因此，对于这两种邮票的集合和上限K=5，答案是M=13。 【输入格式】 输入文件中的第一行：两个整数K和N（1<=K<=200，1<=N<=50）。K是可用的邮票总数，N是邮票面值的数量。 第二行..文件末：N个整数，每行15个，列出所有的N个邮票的面值，面值不超过10000。 【输出格式】 输出文件中的第一行：一个整数，从1分开始连续的可用集合中不多于K张邮票贴出的邮资数。 【输入输出样例】 输入： 5 2 1 3 输出： 13 动态规划题目及其代码By LYLtim 1、数塔问题(tower.pas) 设有一个三角形的数塔，如下图所示。顶点结点称为根结点，每个结点有一个整数数值。从顶点出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。 【样例输入】tower.in 5 {数塔层数} 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 【样例输出】tower.out max=86 【参考程序】 uses math; var n,i,j:byte; a:array[1..10,1..10]of word; f:array[1..10,1..10]of word; begin assign(input,'tower.in');reset(input); assign(output,'tower.out');rewrite(output); readln(n); for i:=1 to n do begin for j:=1 to i do read(a[i,j]); readln; end; fillchar(f,sizeof(f),0); for i:=1 to n do f[n,i]:=a[n,i]; for i:=n-1 downto 1 do for j:=1 to i do f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j]; writeln('max=',f[1,1]); close(input);close(output); end. 2、拦截导弹(missile.pas) 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）， 信息学竞赛中的动态规划专题 哈尔滨工业大学周谷越 【关键字】 动态规划动机状态典型题目辅助方法优化方法 【摘要】 本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。 【目录】 1.动态规划的动机和基本思想 1.1.解决重复子问题 1.2.解决复杂贪心问题 2.动态规划状态的划分方法 2.1.一维状态划分 2.2.二维状态划分 2.3.树型状态划分 3.动态规划的辅助与优化方法 3.1.常见辅助方法 3.2.常见优化方法 4.近年来Noi动态规划题目分析 4.1 Noi2005瑰丽华尔兹 4.2 Noi2005聪聪与可可 4.3 Noi2006网络收费 4.4 Noi2006千年虫 附录参考书籍与相关材料 1.动态规划的动机和基本思想 首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。 1.1 解决重复子问题 对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为∑(log2n / k)。而考虑下面这个问题： USACO 1.4.3 Number Triangles http://122.139.62.222/problem.php?id=1417 【题目描述】 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 在上面的样例中，从7到3到8到7到5的路径产生了最大和：30。 【输入格式】 第一个行包含R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。 【输出格式】 单独的一行包含那个可能得到的最大的和。 【样例输入】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 【样例输出】 30 显然，我们同样可以把大问题化成小问题来解决。如样例中最底层的6就可以从次底层 1、单调递增最长子序列 描述 求一个字符串的最长递增子序列的长度 如：dabdbf最长递增子序列就是abdf，长度为4 输入 第一行一个整数0 2、最长公共子序列 描述 如题，需要写一个程序，得出最长公共子序列。 tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。 输入 第一行给出一个整数N(0 3、括号匹配 时间限制：1000 ms | 内存限制：65535 KB 描述 给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。 如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的 输入 第一行输入一个正整数N，表示测试数据组数(N<=10) 每组测试数据都只有一行，是一个字符串S，S中只包含以上所说的四种字符， S的长度不超过100 输出 对于每组测试数据都输出一个正整数，表示最少需要添加的括号的数量。每组 测试输出占一行 样例输入 4 [] ([])[] ((] ([)] 样例输出 3 2 模拟试卷 ——第三章动态规划 一、填空题（每小题4分，共20分） 1、动态规划算法的基本要素是（）和（）。 2、（）是动态规划法的变形。 3、（）是最大子段和问题想二维的推广。 4、矩阵连乘问题的算法可由（）设计实现。 5、动态规划算法中，通常不同子问题的个数随问题大小呈（）增长。 二、简答题（每小题6分，共30分） 1、写出设计动态规划算法的主要步骤。 2、简述什么是备忘录方法。 3、简述备忘录法与动态规划法的异同。 4、简述动态规划算法的基本思想。 5. 写出最长公共子序列问题具有的性质。 三、综合题（每小题25分，共50分） 1、用动态规划算法实现最长公共子序列问题。 2、用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字 符操作将字符串A转换为字符串B，这里所说的字符操作包括： （1）删除一个字符； （2）插入一个字符； （3）将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d（A,B）。试设计一个有效算法，对任给的两个字符串A和B，计算出它们的编辑距离d（A,B）。 答案 一、填空题 1、最优子结构、子问题重叠 2、备忘录方法 3、最大子矩阵的问题 4、动态规划法 5、多项式 二、简答题 1、（1）找出最优解的性质，并刻画其结构特征； （2）递归地定义最优解； （3）以自底向上的方法计算出最优值； （4）根据计算最优值时得到的信息，构造最优解。 2、备忘录方法是动态规划算法的变形。备忘录方法的控制结构与直接递归方法 的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。 3、与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下 次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。 动态规划习题 Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】 动态规划专题分类视图数轴动规题： 题1.2001年普及组第4题--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0 对于100%的数据,砝码的种类n满足:1≤n≤100; 对于30%的数据,砝码的总数量C满足:1≤C≤20; 对于100%的数据,砝码的总数量C满足:1≤C≤100; 对于所有的数据,砝码的总重量W满足:1≤W≤400000; 题3.石子归并-szgb.pas 【问题描述】有一堆石头质量分别为W1,W2,…,Wn.(Wi≤10000),将石头合并为两堆,使两堆质量的差最小。 【输入】输入文件szgb.in的第一行只有一个整数n(1≤n≤50),表示有n堆石子。接下去的n行,为每堆石子质量。 【输出】输出文件szgb.out的只有一行,该行只有一个整数,表示最小的质量差. 【样例输入】 5 5 8 13 27 14 【样例输出】 3 题4.补圣衣 【问题描述】有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示 (A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。 【输入】本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1共s1个数，表示第一件衣服上每个破损修好它所需的时间 第3行，为B1...Bs2共s2个数，表示第二件衣服上每个破损修好它所需的时间 第4行，为C1...Cs3共s3个数，表示第三件衣服上每个破损修好它所需的时间 第5行，为D1...Ds4共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60) 【输出】输出一行,为修好四件衣服所要的最短时间。 【样例输入】 1213 5 43 6 243 【样例输出】 20 题5.光光的作业homework.pas/homework.exe 【问题描述】光光上了高中，科目增多了。在长假里，光光的老师们都非常严厉，都给他布置了一定量的作业。假期里，光光一共有的时间是k小时。在长假前，老师们一共给光光布置了n份作业，第i份作业需要的时间是ti小时。但是由于老师们互相不 第一小节 动态规划问题 ——最短路径问题 一 在正式提出动态规划法前我们先看一个数学例子： 例1：在 x 1+x 2+x 3+…+x n =a 是约束条件下，求n x x x z +++= 21的极大值. 令 a x a f ==max )(1 ( 0a x ≤≤ ) )m a x ())(max()(12x a x x a f x a f -+=-+= 令 x a x y -+= 且0) (22121=---= -- =x a x x x a x a x dx dy 可得a -x=x, 所以 x=a/2 故 a a a a f 22 2)(2=+= 同理 ))(2max()(max()(23x a x x a f x a f -+=-+= 令 )(2x a x y -+= 0) (222221=---=--=x a x x x a x a x dx dy 所以 a -x=2x , x=a/3 所以 f 3(a)=a a a a a f 33 1 331231)(3==+= 用数学归纳法可以证明：f n (a) =na , x 1=x 2=x 3=…=x n =n a 证明：1：n=1 … 2：设f n (a) =na , x 1=x 2=x 3=…=x n =n a 成立，则 f n+1(a)=max(x +f n (a-x))=max( )(x a n x -+) 令 y=)(x a n x -+ y ’= x 21 x a n -2= 0) (2=---x a x nx x a 所以 nx=a-x ,(n+1)x=a x= 1 +n a f n+1(a)= 1+n a +n 1 +n a =a n )1(+ 我们刚才的解题策略是：“摸着石头过河”，f2 利用f1的结果，f3又利用f2的结果。。。。。。 类似于游戏中的一个勇士打败了一些敌人后得到一件武器，然后去打败另一个强大一些的对手，得到一件更好的武器，接着打败更强大的敌人。。。。。最后取得胜利。。。 在实际生活中，有这么一类问题，它们的活动过程可分为若干个阶段，而且在任一阶段 后的行为仅依赖于第I 阶段的过程状态，而与I 阶段之前的过程如何达到这种过程如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。在50年代，贝尔曼（Richard Bellman ）等人根据这类问题的多阶段决策的特性，提出了解决问题的“最优性原理”从而创建了最优化问题的一种最新的算法设计方法——动态规划。 分治法和动态规划法的比较 动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求 动态规划入门练习题 1.石子合并 在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20). (1)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小; (2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最大; 输入数据: 第一行为石子堆数N; 第二行为每堆的石子数,每两个数之间用一个空格分隔. 输出数据: 从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示. 输入输出范例: 输入: 4 4 5 9 4 输出: －４５９－４ －８－５９ －１３－９ ２２４－５－９４ ４－１４－４ －４－１８ ２２ 最小代价子母树设有一排数，共ｎ个，例如：22 14 7 13 26 15 11.任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小. 输入、输出数据格式与“石子合并”相同。 输入样例： 4 12 5 16 4 输出样例： －１２－５１６４ １７－１６－４ －１７－２０ ３７ 2.背包问题 设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为ＸＫ，今从ｎ种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于ＸＫ，而价值的和为最大。 输入数据： 第一行两个数：物品总数Ｎ，背包载重量ＸＫ；两个数用空格分隔； 第二行N个数,为Ｎ种物品重量；两个数用空格分隔； 第三行N个数,为N种物品价值; 两个数用空格分隔； 输出数据： 第一行总价值； 以下N行，每行两个数，分别为选取物品的编号及数量； 输入样例： 4 10 2 3 4 7 1 3 5 9 输出样例： 12 2 1 4 1 3.商店购物 某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU ;2个花瓶加1朵花是10 ICU不是12 ICU。 编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU 因为: 1朵花加2个花瓶: 优惠价:10 ICU 2朵花正常价: 4 ICU 输入数据 用两个文件表示输入数据。第一个文件INPUT．TXT描述顾客所购物品（放在购物筐中）;第二个文件描述商店提供的优惠商品及价格（文件名为OFF ER．TXT）。两个文件中都只用整数。 第一个文件INPUT．TXT的格式为:第一行是一个数字B（0≤B≤5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。 C 代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品购买总数，1≤K≤5。P 是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。 第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤9 9），表示共有S 种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤9 99。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤ P≤9999）代表此商品组合的优惠价。当然，优惠价要低于该组合中商品正常价之总和。 输出数据 在输出文件OUTPUT．TXT中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品） 动态规划 1.最佳队形（bestqueue; 时限:1s; 128MB） 【题目描述】 要参加复赛了，大家都在体育馆门口集合完毕，由于这次参赛的人数较多，上车前需要排一下队，所有人自愿排成两队（分别定义为A和B队列，人数大于1且两队人数随意），Ms. Zhou给每位同学一张纸，每人默默写下一个字母代表自己，比如：郑逸宁写Z，吴天舒写W等等。 A队： 字母：c m c B队： 字母：s n m n 最佳队形为： 1、每个人前后可以有任意个空位，也可以没有空位； 2、两队在添加空位后长度必须一样，上图可以有多种方案使得A、B两队长度一致， 例如： 3、根据每个人所写的字母，我们定义A队与B队的距离为相应位置上的字母的距离总 和； 4、两队相应位置的距离定义为： （1）两个非空位的距离定义为它们的所写字母ASCII码的差的绝对值； （2）空位与其他任意非空位之间的距离为已知的定值K； （3）空位与空位的距离为0。 5、最佳队形为：在A、B的所有可能队形中，必定存在两个等长的队A’、B’，使得A’ 与B’之间的距离达到最小，这个队形就是最佳队形。 请你写一个程序，求出最佳队形时，A队与B队的距离。 【输入数据】 输入文件第一行为队列A每个人所写字母组成的字符串A； 第二行为队列B每个人所写字母组成的字符串B。（约定：A、B均由小写字母组成且长度均不超过2000）。 第三行为一个整数K（1≤K≤100），表示空位与非空位的距离。 【输出数据】 输出文件仅一行包含一个整数，表示所求得最佳队形A、B之间的距离。 【样例】 bestqueue.in bestqueue.in cmc 10 snmn 2 2. 数学作业（homework; 时限:1s; 128MB） 【问题描述】 数学竞赛刚刚结束，据说题目很难，不过信息学里面的数学题也不容易哦，题目描述很简单：求：方程x1+2x2+…+nx n=m的所有非负整数解（x1,x2,…,x n）的个数。例如，方程：x1+2x2+3x3+4x4+5x5=5有7组解：（5,0,0,0,0）、（3,1,0 ,0,0）、…、（0,0,0,0,1）。 运用你的数学思维加上强大的信息学能力，试试解决它吧！ 【输入数据】 2个整数n，m 【输出数据】 方程非负整数解的个数ans，如果解超过10^9，只需输出ans mod 10^9。动态规划习题
动态规划47题
动态规划题目和代码
动态规划习题精讲
动态规划典型例题
动态规划模拟试卷及答案
动态规划习题完整版
北航 动态规划03级考试题目
经典的动态规划入门练习题
动态规划试题
相关主题
文本预览