动态规划
Dynamic Programming
Starfish (starfish.h@https://www.doczj.com/doc/4218184741.html,)
摘要
本文介绍了动态规划的基本思想和基本步骤，通过实例研究了利用动态规划设计算法的具体途径，讨论了动态规划的一些实现技巧，并将动态规划和其他一些算法作了比较，最后还简单介绍了动态规划的数学理论基础和当前最新的研究成果。
目录
?引言
?动态规划的基本概念
?动态规划的基本定理和基本方程
?动态规划的适用条件
?动态规划的基本思想
?动态规划的基本步骤
?动态规划的实例分析
?动态规划的技巧
?动态规划实现中的问题
?动态规划与其他算法的比较
?动态规划的理论基础
?其他资料
参考文献
?现代计算机常用数据结构和算法，潘金贵编著，南京大学出版社,1992
?算法与数据结构，傅清祥王晓东编著，电子工业出版社,1998
?现代应用数学手册——运筹学与最优化理论卷，清华大学出版社，1998
?运筹学基础，张莹，清华大学出版社，1995
?Dictionary of Algorithms, Data Structures, and Problems ，Paul E. Black ，https://www.doczj.com/doc/4218184741.html,/dads/ , 下载该网站的镜像（1,682KB）
?以下是来自IOI国家集训队的论文：
o动态规划，方奇(下载压缩过的MS Word文档)
o把握本质，灵活运用——动态规划的深入探讨，来煜坤(下载压缩过的MS Word文档)
o动态规划的深入讨论，李刚(下载压缩过的MS Word文档)
o动态规划的特点及其应用，张辰(下载压缩过的MS Word文档)
?AXIOMS FOR DYNAMIC PROGRAMMING , Prakash P. Shenoy ,1996 (下载压缩过的PDF文档)
?Dynamic Programming: a different perspective , Sharon Curtis, (下载压缩过的PDF文档)
一．动态规划的基本概念
动态规划的发展及研究内容
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家
R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
多阶段决策问题
多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。
例1是一个多阶段决策问题的例子，下面是另一个多阶段决策问题的例子：[例2]生产计划问题
工厂生产某种产品，每单位(千件)的成本为1(千元)，每次开工的固定成本为3(千元)，工厂每季度的最大生产能力为6(千件)。经调查，市场对该产品的需求量第一、二、三、四季度分别为 2，3，2，4(千件)。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本(少付固定成本费)，但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5(千元)。还
规定年初和年末这种产品均无库存。试制订一个生产计划，即安排每个季度的产量，使一年的总费用(生产成本和存储费)最少。
决策过程的分类
根据过程的时间变量是离散的还是连续的，分为离散时间决策过程
(discrete-time decision process)，即多阶段决策过程和连续时间决策过程(continuous-time decision process)；根据过程的演变是确定的还是随机的，分为确定性决策过程(deterministic decision process)和随机性决策过程(stochastic decision process)，其中应用最广的是确定性多阶段决策过程。动态规划模型的基本要素
一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：
1.阶段
阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示。在例1中由
A出发为k=1，由B
i (i=1,2)出发为k=2，依此下去从D
i
(i=1,2,3)出发为k=4，共
n=4个阶段。在例2中按照第一、二、三、四季度分为k=1,2,3,4，共4个阶段。
2.状态
状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。
描述状态的变量称状态变量(state variable)。变量允许取值的范围称允许状态集合(set of admissible states)。用x
k
表示第k阶段的状态变量，它可以是
一个数或一个向量。用X
k 表示第k阶段的允许状态集合。在例1中x
2
可取B
1
，
B 2，X
2
={B
1
,B
2
}。
n个阶段的决策过程有n+1个状态变量，x
n+1表示x
n
演变的结果，在例1中x
5
取
E。
根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。
状态变量简称为状态。
3.决策
当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)，在最优控制问题中也称为控制(control)。 描述决策的变量称决策变量(decision variable)。变量允许取值的范围称允许决策集合(set of admissible decisions)。用u k (x k )表示第k 阶段处于状态x k 时的决策变量，它是x k 的函数，用U k (x k )表示了x k 的允许决策集合。在例1中u 2(B 1)可取C 1,C 2,C 3。 决策变量简称决策。
4.策略
决策组成的序列称为策略(policy)。由初始状态x 1开始的全过程的策略记作p 1n (x 1)，即p 1n (x 1)={u 1(x 1),u 2(x 2),...，u n (x n )}。由第k 阶段的状态x k 开始到终止状态的后部子过程的策略记作p kn (x k )，即p kn (x k )={u k (x k ),u k+1(x k+1),...，u n (x n )}。类似地，由第k 到第j 阶段的子过程的策略记作p kj (x k )={u k (x k ),u k+1(x k+1),...，u j (x j )}。对于每一个阶段k 的某一给定的状态x k ，可供选择的策略p kj (x k )有一定的范围，称为允许策略集合(set of admissible policies)，用P 1n (x 1),P kn (x k ),P kj (x k )表示。
5.状态转移方程
在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equation of state)表示这种演变规律，写作
在例1中状态转移方程为：x k+1=u k (x k )
6.指标函数和最优值函数
指标函数(objective function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k 到阶段n 的指标函数用V kn (x k ,p kn (x k ))表示，k=1,2,...,n 。 能够用动态规划解决的问题的指标函数应具有可分离性，即V kn 可表为x k ,u k ,V k+1 n 的函数，记为：
其中函数是一个关于变量V k+1 n 单调递增的函数。这一性质保证了最优化原理
(principle of optimality)的成立，是动态规划的适用前提。
过程在第j 阶段的阶段指标取决于状态x j 和决策u j ，用v j (x j ,u j )表示。阶段k 到阶段n 的指标由v j (j=k,k+1,..n)组成，常见的形式有： 阶段指标之和，即
阶段指标之积，即
阶段指标之极大(或极小)，即
这些形式下第k 到第j 阶段子过程的指标函数为V kj (x k ,u k ,x k+1,...,x j+1)。可以发现，上述(3)-(5)三个指标函数的形式都满足最优性原理。在例1中指标函数为(3)的形式，其中v j (x j ,u j )是边
根据状态转移方程，指标函数V kn 还可以表示为状态x k 和策略p kn 的函数，即V kn (x k ,p kn )。在x k 给定时指标函数V kn 对p kn 的最优值称为最优值函数(optimal value function)，记作f k (x k )，即
其中opt 可根据具体情况取max 或min 。上式的意义是，对于某个阶段k 的某个状态x k ，从该阶段k 到最终目标阶段n 的最优指标函数值等于从x k 出发取遍所有能策略p kn 所得到的最优指标值中最优的一个。
7.最优策略和最优轨线
使指标函数V kn 达到最优值的策略是从k 开始的后部子过程的最优策略，记作p kn *={u k *,..u n *},p 1n *又是全过程的最优策略，简称最优策略(optimal policy)。从
初始状态x 1(=x 1*)出发，过程按照p 1n *
和状态转移方程演变所经历的状态序列{x 1*,x 2*,..,x n+1*}称最优轨线(optimal trajectory)。
二 。动态规划的基本定理和基本方程
动态规划发展的早期阶段，从简单逻辑出发给出了所谓最优性原理，然后在最优策略存在的前提下导出基本方程，再由这个方程求解最优策略。后来在动态规划的应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价，二者之间也不存在任何确定的蕴含关系。基本方程在动态规划中起着更为本质的作用。
[基本定理]
对于初始状态x
1∈X
1
，策略p
1n
*={u
1
*,..u
n
*}是最优策略的充要条件是对于任意的
k,1 [推论] 若p 1n *∈P 1n (x 1 )是最优策略，则对于任意的k,1 kn *对于由x 1 和 p 1,k-1*确定的以x k *为起点的第k到n后部子过程而言，也是最优策略。 上述推论称为最优化原理，它给出了最优策略的必要条件，通常略述为：不论过去的状态和决策如何，对于前面的决策形成的当前的状态而言，余下的各个决策必定构成最优策略。 根据基本定理的推论可以得到动态规划的基本方程： 其中是决策过程的终端条件，为一个已知函数。当x n+1只取固定的状态时称固定终端；当x n+1可在终端集合X n+1中变动时称自由终端。最终要求的最优指标函数满足(10)式： (9)式是一个递归公式，如果目标状态确定，当然可以直接利用该公式递归求出最优值（这种递归方法将在后文介绍，称作备忘录法），但是一般在实际应用中我们通常将该递归公式改为递推公式求解，这样一般效率会更高一些。 三．动态规划的适用条件 任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。 1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。 图2 例如图2中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J 必是从B到C的最优路线。这可用反证法证明：假设有另一路径J'是B到C的最优路径，则A到C的路线取I和J'比I和J更优，矛盾。从而证明J'必是B 到C的最优路径。 最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。动态规划的最优化理在其指标函数的可分离性和单调性中得到体现。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。 可以看出，例1是满足最优化原理的。 2.无后向性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。 如果用前面的记号来描述无后向性，就是：对于确定的x k ，无论p 1,k-1 如何，最 优子策略p kn *是唯一确定的，这种性质称为无后向性。 [例3]Bitonic旅行路线问题 欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的最短游历路线问题。图3(a)给出了七个点问题的解。Bitonic旅行路线问题是欧几里德 货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图3（b）给出了七个点问题的解。 图3 这两个问题看起来很相似。但实质上是不同的。为了方便讨论，我将每个顶点标记了号码。由于必然经过最右边的顶点7，所以一条路(P1-P2)可以看成两条路（P1-7）与(P2-7)的结合。所以，这个问题的状态可以用两条道路结合的形式表示。我们可以把这些状态中，两条路中起始顶点相同的状态归于一个阶段，设为阶段[P1,P2]。 那么，对于Bitonic旅行路线问题来说，阶段[P1,P2]如果可以由阶段[Q1,Q2]推出，则必须满足的条件就是:P1 有些问题乍一看好像有后向性，但如果按照某种合理的方式重新划分阶段，就可以发现其本质上是无后向性的，所以关键是阶段的合理划分，这一点将在动态规划的技巧中详细阐述。 3.子问题的重叠性 在例1中我们看到，动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。以Bitonic旅行路线问题为例，这个问题也可以用搜索算法来解决。动态规划的时间复杂度为 O(n2)，搜索算法的时间复杂度为O(n!) ，但从空间复杂度来看，动态规划算法为O(n2)，而搜索算法为O(n)，搜索算法反而优于动态规划算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。 设原问题的规模为n，容易看出，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划法显得特别有意义，此时动态规划法具有线性时间复杂性。所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。 四．动态规划的基本思想 前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。 动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。 由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。 解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。 因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。 五．动态规划算法的基本步骤 设计一个标准的动态规划算法，通常可按以下几个步骤进行： 1.划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这 若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就 无法用动态规划求解。 2.选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态 表示出来。当然，状态的选择要满足无后效性。 3.确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和 状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导 出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来 了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系 来确定决策。 4.写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用 形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这 一步还是比较简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下： 标准动态规划的基本框架 1. 对f n+1(x n+1 )初始化; {边界条件} 2. for k:=n downto 1 do 3. for 每一个x k ∈X k do 4. for 每一个u k ∈U k (x k ) do begin 5. f k (x k ):=一个极值; {∞或－∞} 6. x k+1:=T k (x k ,u k ); {状态转移方程} 7. t:=φ(f k+1(x k+1 ),v k (x k ,u k )); {基本方程(9)式} 8. if t比f k (x k )更优 then f k (x k ):=t; {计算f k (x k )的最优值} end; 9. t:=一个极值; {∞或－∞} 10. for 每一个x 1∈X 1 do 11. if f 1(x 1 )比t更优 then t:=f 1 (x 1 ); {按照10式求出最优指标} 12. 输出t; 但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行： 1.分析最优解的性质，并刻划其结构特征。 2.递归地定义最优值。 3.以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。 4.根据计算最优值时得到的信息，构造一个最优解。 步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。 六．动态规划的实例分析 下面我们将通过实例来分析动态规划的设计步骤和具体应用。例1已经在前文介绍过了。例1和例2是标准的动态规划，有明显的阶段和状态转移方程；例3、例4、例5、例6是没有明显阶段划分的动态规划，也是一般常见的形式，其中对例4、例5、例6作了比较详细的分析；例7是比较特殊的动态规划，例8是两重动态规划（即为了解决问题要进行两次动态规划）的例子。 [例1] 最短路径问题 [例2]生产计划问题 问题描述 参考解答 这是一个明显的多阶段问题，我们按照计划时间自然划分阶段，状态定义为每阶 段开始时的存储量x k ，决策为每个阶段的产量u k ，记每个阶段的需求量（已知） 为d k ，则状态转移方程为： 设每个阶段开工固定成本费用为a，生产单位数量产品的成本为b，每阶段单位数量产品的存储费用为ｃ，阶段指标为阶段的生产成本费用和存储费用之和，即： 指标函数V kn 为v k 之和，最优值函数f k (x k )为从第k阶段的状态x k 出发到过程终 结的最小费用，满足 其中允许决策集合U 由每阶段的最大生产能力决定，设过程终结时允许存储量 k ，则终端条件为： 为x0 n+1 将以上各式代入到标准动态规划的框架中，就可以求得最优解。 [例3] Bitonic旅行路线问题 问题描述 欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的游历路线问题。图1(a)给出了七个点问题的解。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图1（b）给出了七个点问题的解。 图1 请设计一种多项式时间的算法，解决Bitonic旅行路线问题。 参考解答 首先将n个点按X坐标递增的顺序排列成一个序列L=<点1，点2，…，点n>。显然L[n]为最右点，L[1]为最左点。由于点1往返经过二次(出发一次，返回一次)，因此点1拆成两个点：L[0]=L[1]=点1。 设： W i,j -- 边 ?W i..j -- j-i条连续边 ?d[i] --从点i出发由左至右直到n点后再由右至左到达点i-1的最短距离。d[i]的递归式如下: 我们专门设置了一张记忆表k[i](1≤i≤n)，记下使得d[i]最小的J值。显然递归式的边界d[n]=W n,n-1 ，k[n]=n 。 由d[i]的递归式和记忆表k[i]的定义可以看出，在由点i-1至点i的最短路上，点i至k[i]的子路径上的点序号是遂一递增的，为由左至右方向上的连续子路径。按照递归定义，若k[i]≠N且k[k[i]+1]≠N，则点k[k[i]+1]+1至点 k[k[k[i]+1]+1]也是由左至右方向上的连续子路径；否则k[k[i]+1]至k[i]+1为由右至左方向上的连续子路径，该子路径上的点序号是遂一递减的。 显然要使d[i]最小，必须分别使d[i+1]…d[n-1],d[n]最小,d[i]包含了 d[i+1]…d[n]最小的子问题，因此该问题具有最优子结构和重叠子问题性质，满足动态规划法适用的条件。为了提高算法效率，我们从d[n]出发，运用动态规划方法依次求d[n-1],d[n-2],…,d[1]，充分利用重叠子问题。最后求得的d[1]便是最短游历路线的距离；从点1出发，顺着记忆表k的指示可以递归递输出这条游历路线。 [例4]计算矩阵连乘积 问题描述 在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB 是一个p×r的矩阵。其标准计算公式为： 由该公式知计算C=AB总共需要pqr次的数乘。 现在的问题是，给定n个矩阵{A 1,A 2 ,…,A n }。其中A i 与A i+1 是可乘的，i=1,2,…,n-1。 要求计算出这n个矩阵的连乘积A 1A 2 …A n 。 由于矩阵乘法满足结合律，故连乘积的计算可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序已完全确定，也就是说该连乘积已完全加括号，则我们可以通过反复调用两个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： 1.单个矩阵是完全加括号的； 2.若矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连 乘积B和C的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2 A 3 A 4 可以有以下5种不同的完全加括号方式： (A 1(A 2 (A 3 A 4 )))， (A 1((A 2 A 3 )A 4 )), ((A 1A 2 )(A 3 A 4 )), ((A 1(A 2 A 3 ))A 4 ), (((A 1A 2 )A 3 )A 4 )。 每一种完全加括号方式对应于一种矩阵连乘积的计算次序，而这种计算次序与计算矩阵连乘积的计算量有着密切的关系。 为了说明在计算矩阵连乘积时加括号方式对整个计算量的影响，我们来看一个计 算3个矩阵{A 1，A 2 ，A 3 }的连乘积的例子。设这3个矩阵的维数分别为10×100， 100×5和5×50。若按第一种加括号方式((A 1A 2 )A 3 )来计算，总共需要 10×100×5+10×5×50=7500次的数乘。若按第二种加括号方式(A 1(A 2 A 3 ))来计算， 则需要的数乘次数为100×5×50+10×100×50=75000。第二种加括号方式的计算量是第一种加括号方式的计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大影响。 于是，人们自然会提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2 ,…,A n }(其中A i 的维数为p i-1 ×p i ，i=1,2,…,n)，如何确定计算矩 阵连乘积A 1A 2 …A n 的一个计算次序(完全加括号方式)，使得依此次序计算矩阵连 乘积需要的数乘次数最少。 说明：计算两个均为n×n的矩阵(即n阶方阵)相乘还有一种Strassen矩阵乘法，利用分治思想将2个n阶矩阵乘积所需时间从标准算法的O(n3)改进到 O(n log7)=O(n2.81)。目前计算两个n阶方阵相乘最好的计算时间上界是O(n2.367)。但无论如何，所需的乘法次数总随两个矩阵的阶而递增。在这道题中只考虑采用标准公式计算两个矩阵的乘积。 参考解答 解这个问题的最容易想到的方法是穷举搜索法。也就是列出所有可能的计算次序，并计算出每一种计算次序相应需要的计算量，然后找出最小者。然而，这样做计算量太大。事实上，对于n 个矩阵的连乘积，设有P(n)个不同的计算次序。由于我们可以首先在第k 个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,2,…,n -1；然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号，得到原矩阵序列的一种完全加括号方式。所以关于P(n)，我们有递推式如下： 解此递归方程可得,P(n)实际上是Catalan 数，即P(n)=C(n-1)，其中， 也就是说，P(n)随着n 的增长是指数增长的。因此，穷举搜索法不是一个有效算法。 下面我们来考虑用动态规划法解矩阵连乘积的最优计算次序问题。此问题是动态规划的典型应用之一。 1.分析最优解的结构 首先，为方便起见，将矩阵连乘积A i A i+1…A j 简记为A i…j 。我们来看计算A 1…n 的一个最优次序。设这个计算次序在矩阵A k 和A k+1之间将矩阵链断开，1<=k 这个问题的一个关键特征是：计算A 1…n 的一个最优次序所包含的计算A 1…k 的次序也是最优的。事实上，若有一个计算A 1…k 的次序需要的计算量更少，则用此次序替换原来计算A 1…k 的次序，得到的计算A 1…n 的次序需要的计算量将比最优次序所需计算量更少，这是一个矛盾。同理可知，计算A 1…n 的一个最优次序所包含的计算矩阵子链A k+1…n 的次序也是最优的。根据该问题的指标函数的特征也可以知道该问题满足最优化原理。另外，该问题显然满足无后向性，因为前面的矩阵链的计算方法和后面的矩阵链的计算方法无关。 2.建立递归关系 对于矩阵连乘积的最优计算次序问题，设计算A i…j ,1≤i≤j≤n，所需的最少数乘次数为m[i,j]，原问题的最优值为m[1,n]。 ?当i=j时，A i…j=A i为单一矩阵，无需计算，因此m[i,i]=0，i=1,2,…,n ； ?当i 的最优次序在A k 和A k+1 之间断开，i≤k m[i,j]=m[i,k]+m[k+1,j]+p i-1p k p j 由于在计算时我们并不知道断开点A的位置，所以A还未定。不过k的位置只有j-i个可能，即k∈{i,i+1,…,j-1}。因此k是这j-i个位置中计算量达到最小的那一个位置。从而m[i,j]可以递归地定义为： m[i,j]给出了最优值，即计算A i…j 所需的最少数乘次数。同时还确定了计算 A i…j 的最优次序中的断开位置k，也就是说，对于这个k有m[i,j] = m[i,k] + m[k+1,j] + p i-1p k p j 。若将对应于m[i,j]的断开位置k记录在s[i,j]中，则相应 的最优解便可递归地构造出来。 3.计算最优值 根据m[i,j]的递归定义(2.1)，容易写一个递归程序来计算m[1,n]。稍后我们将看到，简单地递归计算将耗费指数计算时间。然而，我们注意到，在递归计算过程中，不同的子问题个数只有θ(n2)个。事实上，对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 个。由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规划算法解此问题，可依据递归式(2.1)以自底向上的方式进行计算，在计算过程中，保存已解决的子问题答案，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。 下面所给出的计算m[i,j]动态规划算法中，输入是序列P={p 0,p 1 ,…,p n }，输出 除了最优值m[i,j]外，还有使 m[i,j] = m[i,k] + m[k+1,j] + p i-1p k p j 达到最优的断开位置k=s[i,j]，1≤i≤j≤n 。 Procedure MATRIX_CHAIN_ORDER(p); {计算矩阵链连乘的最优断开位置} var i,j,k,q:integer; begin for j:=1 to n do {矩阵链的长度为n} for i:=j downto 1 do begin if i=j then m[i,j]:=0 else begin m[i,j]:=∞; for k:=i to j-1 do begin q:=m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]; if q begin m[i,j]:=q; s[i,j]:=k; {s[i,j]记录计算A[i..j]的最优断开位置k} end; end; end; end; end; 该算法按照 m[1,1] m[2,2] m[1,2] m[3,3] m[2,3] m[1,3] ... ... ... m[n,n] m[n-1,n] ... .... ... m[1,n] 的顺序根据公式(2.1)计算m[i,j]。 该算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。由此可见，动态规划算法比穷举搜索法要有效得多。 4.构造最优解 算法MATRIX_CHAIN_ ORDER只是计算出了最优值，并未给出最优解。也就是说，通过MATRIX_CHAIN_ORDER的计算，我们只知道计算给定的矩阵连乘积所需的最少数乘次数，还不知道具体应按什么次序来做矩阵乘法才能达到数乘次数最少。 然而，MATRIX_CHAIN_ORDER己记录了构造一个最优解所需要的全部信息。 事实上，s[i,j]中的数k告诉我们计算矩阵链A i…j 的最佳方式应在矩阵A k 和A k+1 之间断开，即最优的加括号方式应为(A 1...k )(A k+1…n )。因此，从s[i,j]记录的信息 可知计算A 1…n 的最优加括号方式为 (A 1…s[1,n] )(A s[1,n]+1…n )。而计算A 1…s[1,n] 的最优加 括号方式为(A 1…s[1,s[1,n]])(A s[1 , s[1,n]]+1…s[1,n] )。同理可以确定计算A s[1,n]+1…n 的最优加括 号方式在s[s[1,n]+1,n]处断开。…照此递推下去，最终可以确定A s[1,n]+1…n 的最优完全加括号方式，即构造出问题的一个最优解。 下面的算法MATRIX_CHAIN_MULTIPLY(A,s,i,j)是按s指示的加括号方式计 算矩阵链A={A 1,A 2 ,…,A n }的子链A i…j 的连乘积的算法。 Procdeure MATRIX_CHAIN_MULTIPLY(A,s,i,j); begin if j>i then begin X←MATRIX_CHAIN_MULTIPLY(A,s,i,s[i,j]); Y←MATRIX_CHAIN_MULTIPLY(A,s,s[i,j]+1,j); return(MATRIX_MULTIPLY(X,Y)); {计算并返回矩阵X*Y的值} end else return(Ai); end; 要计算A 1…n 只要调用MATRIX_CHAIN_MULTIPLY(A,s,1,n)即可。 从算法MATRIX_CHAIN_ ORDER可以看出，该算法的有效性依赖于问题本身所具有的三个重要性质：最优子结构性质，无后向性和子问题重叠性质。一般说来，问题所具有的这三个重要性质是该问题可用动态规划算法求解的基本要素，这对于我们在设计求解具体问题的算法时，是否选择动态规划算法具有指导意义。下面我们着重研究最优子结构性质和子问题重叠性质以及动态规划法的一个变形—备忘录方法。 最优子结构 设计动态规划算法的第1步通常是要刻划最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。 在矩阵连乘积最优计算次序问题中，我们注意到，若A 1…n 的最优完全加括号方式 在A k 和A k+1 之间将矩阵链断开，则由该次序确定的子链A 1…k 和A k+1…n 的完全加括号 方式也是最优的。也就是说该问题具有最优子结构性质。在分析该问题的最优子结构性质时，我们所用的方法是具有普遍性的。我们首先假设由问题的最优解导出的其子问题的解不是最优的，然后再设法证明在这个假设下可构造出一个比原问题最优解更好的解，从而导致矛盾。 在动态规划算法中，问题的最优子结构性质使我们能够以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。同时，它也使我们能在相对小的子问题空间中考虑问题。例如，在矩阵连乘积最优计算次序问题中，子问题空间是输人的矩阵链的所有不同的子链，它们的个数为θ(n2)。因而子问题空间的规模仅为θ(n2)。 重叠子问题 可用动态规划算法求解的问题应具备的另一基本要素是子问题的重叠性质。也就是说，在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常，不同的子问题的个数随输人问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。 为了说明这一点，我们来看在计算矩阵连乘积最优计算次序时，利用公式(2.1)直接计算A i…j 的递归算法。 Function RECURSIVE_MATRIX_CHAIN(P,i,j); begin if i=j then return(0); m[i,j]:=∞; for k:=i to j-1 do begin q:=RECURSIVE_MATRIX_CHAIN(P,i,k)+RECURSIVE_MATRIX_CHAIN(P,k+1,j)+p i-1p k p j ; if q return(m[i,j]); end; 图1 计算A 的递归树 1 (4) 的递归树如图1所示。从该图用算法RECURSIVE_MATRIX_CHAIN(P,1,4)计算A 1 (4) 可以看出，许多子问题被重复计算。 事实上，可以证明该算法的计算时间T(n)有指数下界。设算法中判断语句和赋值语句花费常数时间，则由算法的递归部分可得关于T(n)的递归不等式如下： 因此，当n>1时， 据此，可用数学归纳法证明T(n)≥2n-1=Ω(2n)。 因此，直接递归算法RECURSIVE_MATRIX_CHAIN(P,1,n)的计算时间随n指数增长。相比之下，解同一问题的动态规划算法MATRIX_CHAIN_ORDER (P,1,n)只需计算时间O(n2)。其有效性就在于它充分利用了问题的子问题重叠性质。不同的子问题个数为θ(n2)，而动态规划算法对于每个不同的子问题只计算一次，不是重复计算多次。由此也可看出，当解某一问题的直接递归算法所产生的递归树中，相同的子问题反复出现，并且不同子问题的个数又相对较少时，用动态规划算法是有效的。 备忘录方法 动态规划算法的一个变形是备忘录方法。与动态规划算法一样，备忘录方法用一个表格来保存已解决的子问题的答案，在再碰到该子问题时，只要简单地查看该子问题的解答，而不必重新求解。不同的是，备忘录方法采用的是自顶向下的递 动态规划基本原理 动态规划基本原理 近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目 需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经 不再停留于简单的递推和建模上了。 要了解动态规划的概念，首先要知道什么是多阶段决策问题。 一、多阶段决策问题 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采 取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了 一个过程的活动路线，则称它为多阶段决策问题。 各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供 选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可 以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策 略中间，选取一个最优策略，使在预定的标准下达到最好的效果. 让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从A到D的最 短 图4-1 带权有向多段图 路径的长度(下面简称最短距离)。 我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可 能尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，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， 动态规划练习二 1、乘积最大 [问题描述] 在一次数学智力竞赛活动中，主持人给所有参加竞赛的选手出了一到题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的成绩最大。 同时为了帮助选手能够理解题意，主持人还举了如下一个例子： 有一个数字串：312，当N=3，K=1时有两种分法： （1）3*12=36； （2）31*2=62 这时，符合题目要求的结果是：31*2=62。现在要求设计一个程序，以求得正确的答案。 输入 Input.in文件共有两行：第一行有两个自然数N，K（2<=N<=40, 1<=K<=6）；第二行是一个长度为N的数字串。 输出 一个自然数，即所求得的最大乘积。 输入输出样例 输入（input.in） 4 2 1231 输出（ans.out） 62 2、数字加法问题 [问题描述] 有一个由数字1，2，... ，9组成的数字串（长度不超过200），问如何将M(M<=20)个加号("+")插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。 注意： 加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。 例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。 [输入格式］ 从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），Ｍ的值在输入文件的第二行行首。 [输出格式］ 在屏幕上输出所求得的最小和的精确值。 [输入输出举例］ 82363983742 3 输入输出 2170 实验2 求解二次规划问题 LINDO 可以求解二次规划（QP ）问题。例如： ?? ? ??<=+>++-+=7.011.19.02.1..4.03min 22y y x y x t s y xy y x f 由LAGRANGE 乘子法，得 ()()()7.011.19.02.14.0322-+-++-+-+-+y C y x B y x A y xy y x ， 分别对x 、y 求偏导，得到两个约束条件： 4 .09.020 2.16->++-->+--C B A x y B A y x 在LINDO 中输入下列命令： MIN X+Y+A+B+C ST 6X-Y-1.2A+B>0 2Y-X-0.9A+B+C>-0.4 1.2X+0.9Y>1.1 X+Y=1 Y<0.7 END QCP 4 注释：MIN X+Y+A+B+C 一句只代表变量的出场顺序； QCP 4 一句代表前4行不是原问题真正的约束，原问题真正的约束从第5行开始。 LINDO 运行后输出以下结果：STATUS OPTIMAL QP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION V ALUE 1) 1.355556 V ARIABLE V ALUE REDUCED COST X 0.666667 0.000000 Y 0.333333 0.000000 A 10.888889 0.000000 B 9.400000 0.000000 C 0.000000 0.366667 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -0.666667 3) 0.000000 -0.333333 4) 0.000000 -10.888889 5) 0.000000 9.400000 6) 0.366667 0.000000 NO. ITERATIONS= 7 这个结果说明：LINDO求解此二次规划问题（QP）共用7步迭代得到最优解fmin = 1.355556，X = 0.666667，Y = 0.333333。第5个松弛变量取值0.366667，其它松弛变量都取0值，即，这个最优解使得前4个约束条件都取等号；其对偶问题的最优解（影子价格）DUAL PRICES为Y1 = -0.666667，Y2 = -0.333333，Y3 = -10.888889，Y4 = 9.4，Y5 = 0。 农户生产的优化模型 本文内容取自生产实践，豫东一个普通农户，该农户所在地区的农业生产条件、气候状况属于中等。下列各变量的假设均建立在农村一般农业生产条件、气候状况之上。 假设（面积单位：亩）： X1 = 用于完成上缴国家任务的小麦一年总种植面积 X2 = 用于生产、生活的小麦一年总种植面积 X3 =用于生产、生活的油菜一年总种植面积 X4 =用于生产、生活的红薯一年总种植面积 X5 =用于完成上缴国家任务的棉花一年总种植面积 X6 =用于生产、生活的棉花一年总种植面积 X7 =用于完成上缴国家任务的玉米一年总种植面积 X8 =用于生产、生活的玉米一年总种植面积 X9 =用于生产、生活的芝麻一年总种植面积 X10 =用于生产、生活的花生一年总种植面积 X11 =用于生产、生活的大豆一年总种植面积 X12 =用于生产、生活的西瓜一年总种植面积 X13 =用于生产、生活的番茄一年总种植面积 X14 =用于生产、生活的白菜一年总种植面积 X15 =用于生产、生活的辣椒一年总种植面积 X16 =用于生产、生活的茄子一年总种植面积 序列二次规划法 求解一般线性优化问题: 12min (x) h (x)0,i E {1,...,m }s.t.(x)0,i {1,...,m } i i f g I =∈=?? ≥∈=? (1.1) 基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通过减少价值函数来获取当前迭代点的移动步长，重复这些步骤直到得到原问题的解。 1.1等式约束优化问题的Lagrange-Newton 法 考虑等式约束优化问题 min (x) s.t.h (x)0,E {1,...,m} j f j =∈= (1.2) 其中:,n f R R →:()n i h R R i E →∈都为二阶连续可微的实函数. 记1()((),...,())T m h x h x h x =. 则(1.3)的Lagrange 函数为： 1(,)()*()()*()m T i i i L x u f x u h x f x u h x ==-=-∑ （1.3） 其中12(,,...,)T m u u u u =为拉格朗日乘子向量。 约束函数()h x 的Jacobi 矩阵为：1()()((),...,())T T m A x h x h x h x =?=??. 对（1.3）求导数，可以得到下列方程组： (,)()A()*(,)0(,)()T x u L x u f x x u L x u L x u h x ??? ???-?===?????-???? （1.4） 现在考虑用牛顿法求解非线性方程（1.4）. (,)L x u ?的Jacobi 矩阵为： (,)()(,)() 0T W x u A x N x u A x ?? -= ?-?? 2设计动态规划算法的主要步骤为： （1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。 3. 分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。 贪心选择算法与动态规划算法的异同点：同：都要求问题具有最优子结构性质；异：动态规划算法为自底向上的方式解各子问题，贪心算法为自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择问题就转换为规模更小的字问题。 6. 分治法所能解决的问题一般具有的几个特征是：（1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 P：也即是多项式复杂程度的问题。 NP就是多项式复杂程度的非确定性问题。 NPC(NP Complete)问题 ADT 抽象数据类型 分析问题→设计算法→编写程序→上机运行和测试 算法特性1. 确定性、可实现性、输入、输出、有穷性 算法分析目的2. 分析算法占用计算机资源的 情况，对算法做出比较和评价，设计出额更好 的算法。 3. 算法的时间复杂性与问题的规模相关，是 问题大小n的函数。 算法的渐进时间复杂性的含义：当问题的规模 n趋向无穷大时，影响算法效率的重要因素是 T(n)的数量级，而其他因素仅是使时间复杂度 相差常数倍，因此可以用T(n)的数量级(阶) 评价算法。时间复杂度T(n)的数量级(阶)称为 渐进时间复杂性。 最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 最坏情况下的时间复杂性和平均时间复杂性 考察的是n固定时，不同输入实例下的算法所 耗时间。最坏情况下的时间复杂性取的输入实 例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间 与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 为什么要分析最坏情况下的算法时间复杂 性？最坏情况下的时间复杂性决定算法的优 劣，并且最坏情况下的时间复杂性较平均时间 复杂性游可操作性。 1.贪心算法的基本思想？ 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 贪心选择算法与动态规划算法的异同点：同：都要求问题具有最优子结构性质；异：动态规划算法为自底向上的方式解各子问题，贪心算法为自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择问题就转换为规模更小的字问题。 01背包问题的动态规划算法、蛮力法和空间优化算法 算法思想： （1）【导师实战恋爱教-程】、动态规划算法：解决背包物品价值最大化问题的最优解，是建立在每一个子问题的最优解的前提下完成的。设Valu【扣扣】e[i,j]表示的是i个物品放进背包容量为j的背包的价值，令i从0【⒈】增至n（物品总数量），j从0增至c（背包总容量）。Value[n,c]就是我【О】们要的背包价值最大化的解。为了得到这个解必须要把之前的都解【１】决，每一个问题的最优解的算法又根据以下确定：当物品重【６】量w小于背包体积j时，此物品不放进背包，价值与上一次【⒐】价值相同；当物品重量w不小于背包体积j时，此物品是否放进背【５】包，取决于Value[i-1,j]和Value[i-1,j-w]+v的大小。写成表达式【２】则为以下内容： ? Va【б】lue[i-1,j]? weight[i]j Value[i,j] ? Max(Value[i-1,j],Value[i-1,j-w[i]]+v[i])? weight[i]=j 而这个表达式的约束条件就是当物品数量为0（i=0）时和背包容量为0（j=0）时，最大价值为0。 （2）、空间优化算法：动态规划法的空间复杂度为O（nw），现将空间复杂度优化到O（w）。我使用的方法为建立一个新的一维数组V[w+1]，此数组与上述动态规划的Value数组不同的是只用于记录上一行的价值，如 当我需要求第i行的价值的时候，v数组中存放的是第i-1行的价值。然后从后往前（背包容量从c到0）计算价值、覆盖数组，因为每一次计算背包容量j大小的价值可能会用到j-w的价值，如果从前往后计算的话则数组已被更新，所以要从后往前计算。计算价值的方法也是和上面大致相同：如果物品体积w小于背包容量j，则判断V [j]和V[j-w]+v的大小;如果大于背包容量，则放不进去，V[j]价值不变。 写成表达式如下： ? V[j]? weight[i]j ? Max(V[j],V[j-w[i]]+value[i])? weight[i]=j 由于使用一维数组的方法，内容还一直被覆盖，所以无法得出背包中具体有哪些物品。 （3）、穷举法：用于验证动态规划方法是否正确。以n=4为例，创建一个v[4]的数组，用0和1表示第i个物品是否放进背包，如0001表示只有第四个物品放进背包。然后数组从0000~1111，计算每次摆放的重量以及价值。如果重量小于背包重量，且价值大于当前最大价值，则记录当前的最大价值以及数组。原理是这样在实施的时候为了记录背包的解，将0000和1111看成0和15的二进制形式，所以让i从0到15进行增长，每次将i转换成二进制格式放进数组中，这样做就可以记录最大价值时的i，转换成二进制则可获得具体物品。 伪代码如下： For i 0~2n-1 2.6基本算法之动态规划 01（）1775:采药 总时间限制: 1000ms 内存限制: 65536kB 描述 辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。 如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？ 输入 输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的 M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示 采摘某株草药的时间和这株草药的价值。 输出 输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。 样例输入 70 3 71 100 69 1 1 2 样例输出 3 来源 NOIP 2005 1944:吃糖果 总时间限制: 1000ms 内存限制: 65536kB 描述 名名的妈妈从外地出差回来，带了一盒 好吃又精美的巧克力给名名（盒内共有 N 块巧克力，20 > N >0）。妈妈告 诉名名每天可以吃一块或者两块巧克 力。假设名名每天都吃巧克力，问名名 共有多少种不同的吃完巧克力的方案。 例如：如果N=1，则名名第1天就吃 掉它，共有1种方案；如果N=2，则 名名可以第1天吃1块，第2天吃1 块，也可以第1天吃2块，共有2种 方案；如果N=3，则名名第1天可以 吃1块，剩2块，也可以第1天吃2 Farmer John's farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 <= ncows <= 2000. FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at least F (1 <= F <= N) fields, where F given as input. Calculate the fence placement that maximizes the average, given the constraint. Input * Line 1: Two space-separated integers, N and F. * Lines 2..N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on. Output * Line 1: A single integer that is 1000 times the maximal average.Do not perform rounding, just print the integer that is 1000*ncows/nfields. Sample Input 10 6 6 4 2 10 3 8 5 9 4 1 Sample Output 6500 动态规划基本原理 近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。 要了解动态规划的概念，首先要知道什么是多阶段决策问题。 一、多阶段决策问题 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。 各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果. 让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从A到D的最短 图4-1 带权有向多段图 路径的长度(下面简称最短距离)。 我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可能尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，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。 二、动态规划的术语 1．阶段 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k 表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。 在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。 2．状态 状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。 在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。 过程的状态通常可以用一个或”一组数”来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。 当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。 3．无后效性 我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发 2、对于二次规划模型求解： 问题1： 先求出ij c ，结果如下表： 330.7 320.3 300.2 258.6 198 180.5 163.1 181.2 224.2 252 256 266 281.2 288 302 370.7 360.3 345.2 326.6 266 250.5 241 226.2 269.2 297 301 311 326.2 333 347 385.7 375.3 355.2 336.6 276 260.5 251 241.2 203.2 237 241 251 266.2 273 287 420.7 410.3 395.2 376.6 316 300.5 291 276.2 244.2 222 211 221 236.2 243 257 410.7 400.3 380.2 361.6 301 285.5 276 266.2 234.2 212 188 206 226.2 228 242 415.7 405.3 385.2 366.6 306 290.5 281 271.2 234.2 212 201 195 176.2 161 178 435.7 425.3 405.2 386.6 326 310.5 301 291.2 259.2 237 226 216 198.2 185 162 由于二次规划模型中约束条件151 {0}[500,],1,2,7,ij i j X s i =∈=∑的存 在，必须加以处理。引进0-1变量15,...2,1,=i n i ，则 151{0}[500,],1,2,7,ij i j X s i =∈=∑可以等价转换为下面的三个约束条件： i j ij s X ≤∑=151 i j ij Mn X ≤∑=151 i j ij n X *500151≥∑= 其中M 为一个很大数。 这样就可以得到下面的lingo 程序： sets : s/1..7/:sx; a/1..15/:z,y,n,t; links(s,a):c,x; endsets 动态规划的基本概念 基本概念 设我们研究某一个过程,这个过程可以分解为若干个互相联系的阶段。每一阶段都有其初始状态和结束状态,其结束状态即为下一阶段的初始.状态。第一阶段的初始状态就是整个过程的初始状态,最后一阶段的结束状态就是整个过程的结束状态。在过程的每一个阶段都需要作出决策,而每一阶段的结束状态依赖于其初始状态和该阶段的决策。动态规划问题就是要找出某种决策方法, 使过程达到某种最优效果。 这种把问题看作前后关联的多阶段过程称为多阶段决策过程, 可用图9.1表示。下面介绍动态规划的术语和基本概念。 (l)阶段 把所研究的过程恰当地分为若干个互相联系的相对独立过程。 (2)状态变量 用来描述系统所处状态的变量称为状态变量。通常用s k 表示第k 阶段的初始状态，则s k +1表示第k 阶段结束时(也就是第k+l 阶段开始时)过程的状态。 通常要求状态变量具有无后效性, 即过程在第k 阶段以后的变化只与该阶段结束时的状态有关, 而与系统如何到达此状态的过程无关。 (3)决策变量的状态转移方程。系统在第k 阶段中的变化过程, 通常我们并不关心，但我们希望知道该阶段的初始状态与结束状态之间的关系。我们用以影响该系统的手段，也用一个变量x k 表示，称为决策变量， 则第k 阶段结束时的状态s k +1是决策变量x k 和初始状态s k 的函数, 即 s k +1=T (s k ,x k ) (9-1) (9-1)称为状态转移方程。 (4)权函数 反映第k 阶段决策变量x k 的效益函数W k (s k ,x k ) 称为权函数。 (5)指标函数 判断整个过程优劣的数量指标称为指标函数。当第k 阶段初始状态为s k 时,设我们在此阶段及以后各阶段均采取最优策略时,所获得的效益为f k (s k ), 那么有 ))}(),,(({)(11++∈=k k k k k k D x k k s f x s W F opt s f k k (9-2) 其中opt 表示最优,按具体问题可取为max 或min , D k 是决策变量x k 的定义域;F k 是某一个函数; s k +1=T (s k ,x k ). 图9.1 §1 二次规划模型 数学模型： ub x lb beq x Aeq b x A x f Hx x T T x ≤≤=?≤?+21min 其中H 为二次型矩阵，A 、Aeq 分别为不等式约束与等式约束系数矩阵，f,b,beq,lb,ub,x 为向量。 求解二次规划问题函数为quadprog( ) 调用格式： X= quadprog(H,f,A,b) X= quadprog(H,f,A,b,Aeq,beq) X= quadprog(H,f,A,b,Aeq,beq,lb,ub) X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) X= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) [x,fval]= quadprog(…) [x,fval,exitflag]= quadprog(…) [x,fval,exitflag,output]= quadprog(…) [x,fval,exitflag,output,lambda]= quadprog(…) 说明：输入参数中，x0为初始点；若无等式约束或无不等式约束，就将相应的矩阵和向量设置为空；options 为指定优化参数。输出参数中，x 是返回最优解；fval 是返回解所对应的目标函数值；exitflag 是描述搜索是否收敛；output 是返回包含优化信息的结构。Lambda 是返回解x 入包含拉格朗日乘子的参数。 例1：求解：二次规划问题 min f(x)= x 1-3x 2+3x 12+4x 22 -2x 1x 2 s.t 2x 1+x 2≤2 -x 1+4x 2≤3 9.2.4 二次规划问题 9.2.4.1 基本数学原理 如果某非线性规划的目标函数为自变量的二次函数，约束条件全是线性函数，就称这种规划为二次规划。其数学模型为： 其中，H, A,和Aeq为矩阵,f, b, beq, lb, ub,和x为向量。 9.2.4.2 相关函数介绍 quadprog函数 功能：求解二次规划问题。 语法： x = quadprog(H,f,A,b) x = quadprog(H,f,A,b,Aeq,beq,lb,ub) x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) [x,fval] = quadprog(...) [x,fval,exitflag] = quadprog(...) [x,fval,exitflag,output] = quadprog(...) [x,fval,exitflag,output,lambda] = quadprog(...) 描述： x = quadprog(H,f,A,b) 返回向量x，最小化函数1/2*x'*H*x + f'*x ， 其约束条件为A*x <= b。 x = quadprog(H,f,A,b,Aeq,beq)仍然求解上面的问题，但添加了等式约束条件 Aeq*x = beq。 x = quadprog(H,f,A,b,lb,ub)定义设计变量的下界lb和上界ub，使得lb <= x <= ub。 x = quadprog(H,f,A,b,lb,ub,x0)同上，并设置初值x0。 x = quadprog(H,f,A,b,lb,ub,x0,options)根据options参数指定的优化参数进行最小 化。 [x,fval] = quadprog(...)返回解x处的目标函数值fval = 0.5*x'*H*x + f'*x。 [x,fval,exitflag] = quadprog(...)返回exitflag参数，描述计算的退出条件。 [x,fval,exitflag,output] = quadprog(...)返回包含优化信息的结构输出output。 [x,fval,exitflag,output,lambda] = quadprog(...)返回解x处包含拉格朗日乘子的 lambda参数。 变量： 各变量的意义同前。 实验报告 课程名称：动态规划 实验名称：二维分配问题 专业：信息与计算科学指导教师：滕宇 完成日期： 2014年 11月 07日 MATLAB程序： clc;clear; P=[0.4 0.1 0.5; 0.2 0.4 0.2]; A=[3 2 5]; M=[6 10]; sv=@(u,w,pi)A(pi)*(1-((1-P(1,pi))^u)*((1-P(2,pi))^w));% 朝第pi目标发送u个第一种导弹，w 个第二种导弹，的价值; lmd=0.7; for ll=1:99 lmd=ll/100; v=@(u,w,pi)sv(u,w,pi)-lmd*w; vu=zeros(7,3);% vk(uk)的值 wi=vu;% 相应的决策 for l=1:3 lv=@(u,w)v(u,w,l); for m=0:6 mv=@(w)lv(m,w); for n=0:10 ff=mv(n); if vu(m+1,l) end end end end %% 动态规划 x=zeros(1,3); u=x; w=x; x(1)=find(fx(:,1)==max(fx(:,1)))-1; u(1)=ui(x(1)+1,1); x(2)=x(1)-u(1); u(2)=ui(x(2)+1,2); x(3)=x(2)-u(2); u(3)=ui(x(3)+1,3); w(1)=wi(u(1)+1,1); w(2)=wi(u(2)+1,2); w(3)=wi(u(3)+1,3); %% 判断是否符合 if sum(u)==6&&sum(w)==10 disp('lmd符合最大价值为'); max(fx(:,1)) disp('方案为'); u w lmd else disp('lmd不符合'); end end 最优化算法实验指导书 2.二次规划求解 例1 求解下面二次规划问题 21212221x 6x 2x x x x 2 1)x (f min ---+= sub.to 2x x 21≤+ 2x 2x 21≤+- 3x x 221≤+ 21x 0,x 0≤≤ 解：x f x H x 2 1)x (f '+'= 则??????--=2111H ，?? ????--=62f ，??????=21x x x 在MA TLAB 中实现如下： >> H = [1 -1; -1 2] ; >> f = [-2,-6]; >> A = [1 1; -1 2; 2 1]; >> b = [2; 2; 3]; >> lb = zeros(2,1); >> [x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[ ],[ ],lb) Warning: Large-scale method does not currently solve this problem formulation, switching to medium-scale method. > In C:\MATLAB6p5\toolbox\optim\quadprog.m at line 213 Optimization terminated successfully. x = 0.6667 1.3333 fval = -8.2222 exitflag = 1 output = iterations: 3 algorithm: 'medium-scale: active-set' firstorderopt: [] cgiterations: [] lambda = lower: [2x1 double] upper: [2x1 double] eqlin: [0x1 double] ineqlin: [3x1 double] 例 1123 2212123min 246y x x x x x =+--- ..s t 1232131232 3 4 ,,0x x x x x x x x x +≤+≤+≤≥ （1）标准形式： 由 2212123246y x x x x x =+--- 22121231(22)2462 x x x x x =+--- 知 200020000H ?? ?= ? ??? 为半正定矩阵，约束不必改动。 （2）在编辑窗口建立一个存放各种信息的M 文件， 在MA TLAB 中实现如下： >> H = [2 0 0;0 2 0;0 0 0]; >> f = [-2 -4 -6]; >> A = [1 1 0; 0 1 1; 1 0 1]; >> b = [2; 3; 4]; >> C =[]; >> d=[]; >> xm=[0; 0; 0]; 实验二用动态规划实现0-1背包问题 一．实验目的 1.熟悉动态规划法的基本原理。 2.通过本次实验加深对动态规划的理解。 二．实验内容及要求 内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为 c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大? 要求：使用动态规划算法编程，求解0-1背包问题 三．程序列表 （1） #include int sum=0; for(int k=n;k>=1;k--) { if(optp[k][m]==optp[k-1][m]) x[k]=0; else { x[k]=1; m=m-w[k]; sum=sum+w[k]; } } x[1]=optp[1][m]?1:0; cout<<"最大总重量:"< 动态规划算法原理 及其应用研究 2012年5月20日摘要：动态规划是解决最优化问题的基本方法，本文介绍了 动态规划的基本思想和基本步骤，并通过几个实例的分析，研究了利用动态规划设计算法的具体途径。关键词：动态规划多阶段决策 1.引言 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一■ 个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten ）。爱尔思先后于1961年和1964年出版了两部 关于动态规划的著作，并于1964年同尼母霍思尔（Nemhause）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数学性质做出了巨大的贡献。 动态规划问世以来，在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径 动态规划入门练习题 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中写一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商品）动态规划基本原理
动态规划练习二
求解二次规划问题
二次规划问题
2设计动态规划算法的主要步骤为
动 态 规 划 算 法 ( 2 0 2 0 )
2.6基本算法之动态规划
动态规划(2)
动态规划基本原理
二次规划解法
动态规划的基本概念
二次_动态规划-图论
二次规划问题
动态规划二维分配问题-MATLAB
二次规划实验举例
实验 2 用动态规划实现0-1背包问题
动态规划算法原理与的应用
经典的动态规划入门练习题
相关主题
文本预览