动态规划习题讲解
第七章动态规划
规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（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
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
动态规划讲解大全(含例题及答案)
动态规划讲解大全 动态规划(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)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么
经典算法——动态规划教程
动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的没计法对不同的问题，有各具特色的表示方式。不存在一种万能的动态规划算法。但是可以通过对若干有代表性的问题的动态规划算法进行讨论，学会这一设计方法。 多阶段决策过程最优化问题 ——动态规划的基本模型 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。 【例题1】最短路径问题。图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少? 【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、 B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。用dk(x k，x k+1)表示在第k阶段由初始状态x k到下阶段的初始状态x k+1的路径距离，Fk(x k)表示从第k阶段的x k到终点E的最短距离，利用倒推方法求解A到E的最短距离。具体计算过程如下： 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{8,10}=8 F3(C2)=d3(C2,D1)+f4(D1)=5+3=8 F3(C3)=d3(C3,D3)+f4(D3)=8+3=11 F3(C4)=d3(C4,D3)+f4(D3)=3+3=6
动态规划习题
第七章动态规划 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划（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），输入称为输入状态，输出称为输出状态。
动态规划练习试题和解答
动态规划练习题 [题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. 样例输入: 样例输出：
动态规划经典教程
动态规划经典教程 引言：本人在做过一些题目后对DP有些感想，就写了这个总结： 第一节动态规划基本概念 一，动态规划三要素：阶段，状态，决策。 他们的概念到处都是，我就不多说了，我只说说我对他们的理解： 如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。 下面举个例子： 要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。 一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。 经过这个例子相信大家对动态规划有所了解了吧。 下面在说说我对动态规划的另外一个理解： 用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。这样对图求最优路径就是动态规划问题的求解。 二，动态规划的适用范围 动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？ 一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件： 最优子结构（最优化原理） 无后效性 最优化原理在下面的最短路径问题中有详细的解答； 什么是无后效性呢？ 就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。 而求状态N时有用到了状态i这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用图论理解动态规划中形成的图无环的原因。 也就是说当前状态是前面状态的完美总结，现在与过去无关。。。 当然，有是换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。 三，动态规划解决问题的一般思路。 拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或贪心了。当却定问题可以用动态规划后，就要用下面介绍的方法解决问题了：（1）模型匹配法： 最先考虑的就是这个方法了。挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动，现在考题办都是基本模型的变形套用时要小心条件，三思而后行。这些基本模型在先面的分类中将一一介绍。 （2）三要素法 仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同： 先确定阶段的问题：数塔问题，和走路问题（详见解题报告） 先确定状态的问题：大多数都是先确定状态的。 先确定决策的问题：背包问题。（详见解题报告） 一般都是先从比较明显的地方入手，至于怎么知道哪个明显就是经验问题了，多做题就会发现。 （3）寻找规律法： 这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有点贪心的意思。 （4）边界条件法 找到问题的边界条件，然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。 （5）放宽约束和增加约束 这个思想是在陈启锋的论文里看到的，具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。 第二节动态规划分类讨论
动态规划习题精讲
信息学竞赛中的动态规划专题 哈尔滨工业大学周谷越 【关键字】 动态规划动机状态典型题目辅助方法优化方法 【摘要】 本文针对信息学竞赛（面向中学生的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 动态规划经典案例详解之背包问题 【摘要】本文主要从动态规划经典案例——背包问题的动态规划设计思路出发，结合具体实例，对动态规划在程序设计中的典型应用以及衍生拓展进行详细分析。 【关键字】动态规划信息学奥赛0/1背包问题 动态规划并非一个算法，而是一种解题的思路，其核心思想是通过使用大量的存储空间把中间结果记录下来，大大减少重复计算的时间，从而提高的程序的执行效率，因为信息学奥林匹克复赛题目的解决程序一般是有时间限制的，对于某些用搜索必然耗费大量时间的题目，动态规划几乎是唯一的选择。但是动态规划并没有一个简单的模型可以套用，对于每个不同的题目都有对应的不同规划思路，我们只能通过对一些动态规划经典案例的学习来训练自己的动态规划思维能力，从而以不变应万变，应付各种复杂的程序设计，本文通过对动态规划经典案例之一的背包问题进行详细阐述，旨在让学生了解动态规划和搜索的不同设计思路以及动态规划的优越性。 【原型例题】 从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。求使物品价值最高的选取方法。 【输入文件】 第一行一个数c，为背包容量。 第二行一个数n，为物品数量 第三行n个数，以空格间隔，为n个物品的重量 第四行n个数，以空格间隔，为n个物品的价值 【输出文件】 能取得的最大价值。 【分析】 初看这类问题，第一个想到的会是贪心，但是贪心法却无法保证一定能得到最优解，看以下实例： 贪心准则1：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2,w=[100,10,10],p=[20,15,15],c=105。当利用价值贪婪准则时，获得的解为x=[1,0,0]，这种方案的总价值为20。而最优解为[0,1,1]，其总价值为30。 贪心准则2：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n=2,w=[10,20], p=[5,100],c=25。当利用重量贪婪策略时，获得的解为x=[1,0],比最优解[0,1]要差。 动态规划习题 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小时。但是由于老师们互相不 动态规划 一·动态规划法的发展及其研究内容 动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解 创立了解决这类过程优化问题的新方法——动态规划。1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。 二·动态规划法基本概念 一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素： 1．阶段 阶段（stage）是对整个过程的自然划分。通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。阶段变量一般用k=….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 动态规划 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。 动态规划入门练习题 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)分析最优值的结构，刻画其结构特征； (2)递归地定义最优值；0 (3)按自底向上或自顶向下记忆化的方式计算最优值。 【例题1】背包问题描述： 有一个负重能力为m的背包和n种物品，第i种物品的价值为v，重量为w。在不超过背包负重能力的前 提下选择若干个物品装入背包，使这些的物品的价值之和最大。每种物品可以不选，也可以选择多个。 假设每种物品都有足够的数量。 分析： 从算法的角度看，解决背包问题一种最简单的方法是枚举所有可能的物品的组合方案并计算这个组合 方案的价值之和，从中找出价值之和最大的方案。显然，这种靠穷举所有可能方案的方法不是一种有效 的算法。 但是这个问题可以使用动态规划加以解决。下面我们用动态规划的逆向思维法来分析这个问题。 (1)背包问题最优值的结构 动态规划的逆向思维法的第一步是刻画一个最优值的结构，如果我们能分析出一个问题的最优值包含 其子问题的最优值，问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用动 态规划的显著特征。 对一个负重能力为m的背包，如果我们选择装入一个第 i 种物品，那么原背包问题就转化为负重能力 为 m-w 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若我们用背包的负重能力来 划分状态，令状态变量s[k]表示负重能力为k的背包，那么s[m]的值只取决于s[k](k≤m)的值。因此背包 动态规划专题分类视图 数轴动规题： (1) 较复杂的数轴动规 (4) 线性动规 (7) 区域动规： (14) 未知的动规： (20) 数轴动规题： 题1.2001年普及组第4题--装箱问题 【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0 的个数，但不包括一个砝码也不用的情况。 【输入格式】输入文件weight.in的第一行只有一个数n,表示不同的砝码的种类数. 第2行至第n+1行,每行有两个整数.第k+1行的两个数分别表示第k种砝码的个数和重量. 【输出格式】输出文件weight.out中只有一行数据:Total=N。表示用这些砝码能秤出的不同重量数。【输入样例】 2 2 2 2 3 【输出样例】 Total=8 【样例说明】 重量2,3,4,5,6,7,8,10都能秤得 【数据限制】 对于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) 1．最大子段和问题：给定整数序列 n a a a ,,,21 ，求该序列形如∑=j i k k a 的子段和 的最大值： ? ?? ???∑=≤≤≤j i k k n j i a 1max ,0max 1) 已知一个简单算法如下： int Maxsum(int n,int a,int& best i,int& bestj){ int sum = 0; for (int i=1;i<=n;i++){ int suma = 0; for (int j=i;j<=n;j++){ suma + = a[j]; if (suma > sum){ sum = suma; besti = i; bestj = j; } } } return sum; }试分析该算法的时间复杂性。 2) 试用分治算法解最大子段和问题，并分析算法的时间复杂性。 3) 试说明最大子段和问题具有最优子结构性质，并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。 （提示：令1()m ax ,1,2,,j k i j n k i b j a j n ≤≤≤===∑ ） 解：1）分析按照第一章，列出步数统计表，计算可得)(2 n O 2）分治算法：将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n]，分别求出 这两段的最大子段和，则a[1:n]的最大子段和有三种可能： ①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同； ②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同； ③a[1:n]的最大子段和为两部分的字段和组成，即 j n j i l n i j a a a a a +++++=+?? ? ???=?? ????∑ 122；动态规划经典案例详解(背包问题)
动态规划习题完整版
动态规划法求解生产与存储问题
动态规划试题
经典的动态规划入门练习题
动态规划理论(精华)
动态规划习题
5 动态规划算法习题答案