下载文档原格式
第6章 动态规划动态规划（Dynamic Programming ）是解决多阶段决策过程最优化的一种有用的数学方法。
它是由美国学者Richard .Bellman 在1951年提出的，1957年他的专著《动态规划》一书问世，标志着运筹学的一个重要分支－动态规划的诞生.动态规划也是一种将多变量问题转化为单变量问题的一种方法。
在动态规划中，把困难的多阶段决策问题变换成一系列相互联系的比较容易的单阶段问题一个个地求解。
动态规划是考察解决问题的一种途径 ,而不是一种特殊的算法，不像线性规划那样有统一的数学模型和算法（如单纯形法）.事实上，在运用其解决问题的过程中还需要运用其它的优化算法。
因此，动态规划不像其它方法局限于解决某一类问题,它可以解决各类多阶段决策问题。
动态规划在工程技术、经济管理等社会各个领域都有着广泛的应用，并且获得了显著的效果。
在经济管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存管理问题、排序问题、设备更新问题以及生产过程最优控制问题等，是经济管理中一种重要的决策技术。
许多规划问题用动态规划的方法来处理,常比线性规划或非线性规划更有效。
特别是对于离散的问题，由于解析数学无法发挥作用，动态规划便成为了一种非常有用的工具。
动态规划可以按照决策过程的演变是否确定分为确定性动态规划和随机性动态规划；也可以按照决策变量的取值是否连续分为连续性动态规划和离散性动态规划。
本教材主要介绍动态规划的基本概念、理论和方法,并通过典型的案例说明这些理论和方法的应用。
6.1动态规划的基本理论6.1.1多阶段决策过程的数学描述有这样一类活动过程,其整个过程可分为若干相互联系的阶段，每一阶段都要作出相应的决策,以使整个过程达到最佳的活动效果。
任何一个阶段(stage ，即决策点)都是由输入(input ）、决策（decision ）、状态转移律（transformation function )和输出(output )构成的，如图6-1（a ）所示.其中输入和输出也称为状态(state ）,输入称为输入状态，输出称为输出状态。
运筹学必考知识点总结在运筹学中，有一些必考的知识点是非常重要的。
这些知识点涵盖了运筹学的基本概念、方法和模型，对于考生来说，掌握这些知识点是至关重要的。
本文将对运筹学的一些必考知识点进行总结，帮助考生更好地备考。
1. 线性规划线性规划是运筹学中的重要方法之一，它通过建立数学模型来解决各种决策问题。
在线性规划中，目标是最大化或最小化一个线性函数，同时满足一系列线性约束条件。
考生需要掌握线性规划的基本理论，包括线性规划模型的建立、单纯形法和对偶理论等内容。
2. 整数规划整数规划是线性规划的扩展，它要求决策变量取整数值。
整数规划在实际应用中有着广泛的用途，因此对于考生来说，掌握整数规划的基本理论和解题方法是必不可少的。
3. 动态规划动态规划是一种用于求解多阶段决策问题的优化方法。
在动态规划中，问题被分解为多个子问题，并且这些子问题之间存在重叠。
考生需要了解动态规划的基本原理、状态转移方程的建立以及动态规划算法的实现。
4. 网络流问题网络流问题是运筹学中的一个重要领域，它涉及到图论和优化算法等多个方面的知识。
在网络流问题中，主要考察最大流、最小割、最短路等问题的求解方法。
5. 效用理论效用理论是运筹学中的一个重要分支，它研究人们在做出决策时的偏好和选择。
效用函数、期望效用、风险偏好等概念是考试中的热点内容。
6. 排队论排队论是研究排队系统的运作规律和性能指标的数学理论。
在排队论中，考生需要了解排队系统的稳定性条件、平衡方程、性能指标的计算方法等。
7. 多目标决策多目标决策是指在考虑多个目标时的决策问题。
在多目标决策中，往往需要考虑到多个目标之间的矛盾和权衡，因此考生需要掌握多目标规划的基本原理和解题方法。
8. 随机规划随机规划是考虑到不确定因素的决策问题。
在随机规划中，目标函数、约束条件等参数都是随机变量，因此需要考虑到风险和概率的因素。
以上是一些运筹学中的必考知识点，考生在备考过程中需要重点关注这些知识点。
一、实验背景动态规划是一种重要的算法设计方法，广泛应用于解决优化问题。
本次实验旨在通过实际操作，加深对动态规划算法的理解，掌握其基本思想，并学会运用动态规划解决实际问题。
二、实验内容本次实验主要包括以下几个内容：1. 动态规划算法概述首先，我们对动态规划算法进行了概述，学习了动态规划的基本概念、特点、应用领域等。
动态规划是一种将复杂问题分解为若干个相互重叠的子问题，并存储已解决子问题的解，以避免重复计算的方法。
2. 矩阵连乘问题矩阵连乘问题是动态规划算法的经典问题之一。
通过实验，我们学会了如何将矩阵连乘问题分解为若干个相互重叠的子问题，并利用动态规划方法求解。
实验过程中，我们分析了问题的最优子结构、子问题的重叠性，以及状态转移方程，从而得到了求解矩阵连乘问题的动态规划算法。
3. 0-1背包问题0-1背包问题是另一个典型的动态规划问题。
在实验中，我们学习了如何将0-1背包问题分解为若干个相互重叠的子问题，并利用动态规划方法求解。
实验过程中，我们分析了问题的最优子结构、子问题的重叠性，以及状态转移方程，从而得到了求解0-1背包问题的动态规划算法。
4. 股票买卖问题股票买卖问题是动态规划在实际应用中的一个例子。
在实验中，我们学习了如何将股票买卖问题分解为若干个相互重叠的子问题，并利用动态规划方法求解。
实验过程中，我们分析了问题的最优子结构、子问题的重叠性，以及状态转移方程，从而得到了求解股票买卖问题的动态规划算法。
三、实验心得1. 动态规划算法的思维方式通过本次实验，我深刻体会到了动态规划算法的思维方式。
动态规划算法的核心是将复杂问题分解为若干个相互重叠的子问题，并存储已解决子问题的解。
这种思维方式有助于我们更好地理解和解决实际问题。
2. 状态转移方程的重要性在动态规划算法中，状态转移方程起着至关重要的作用。
它描述了子问题之间的关系，是求解问题的关键。
通过本次实验，我学会了如何分析问题的最优子结构，以及如何建立合适的状态转移方程。
采药（动态规划背包问题总结）做了NOIP的题，是动态规划背包问题的典例。
采药输⼊格式：第⼀⾏有2个整数T(1≤T≤1000)和M(1≤M≤100)，⽤⼀个空格隔开，T代表总共能够⽤来采药的时间，M代表⼭洞⾥的草药的数⽬。
接下来的M⾏每⾏包括两个在1到100之间（包括1和100）的整数，分别表⽰采摘某株草药的时间和这株草药的价值。
输出格式：1个整数，表⽰在规定的时间内可以采到的草药的最⼤总价值。
状态转移⽅程：vis[i][j]=vis[i-1][j-xt[i]]+xw[i],当j>=xt[i];vis[i][j]=vis[i-1][j],当j<xt[i];其中vis[i][j]表⽰采摘前i个药时最⼤花费j时所能得到的最⼤价值，xw[i]是第i个药的价值,xt[i]是第i个药的费时。
代码如下：for(int i=1;i<=m;i++)for (int j = 1;j <= t;j++){if (j >= xt[i])vis[i][j] = max(vis[i - 1][j - xt[i]] + xw[i], vis[i - 1][j]);elsevis[i][j] = vis[i - 1][j];}我们可以发现，vis数组每次i递进1时只⽤到上⼀层的i-1，所以可以⽤滚动数组替换，因为⼤的j(vis[i][j])在计算时要⽤到⼩的j(vis[i-1][j-?])，故要从t向下开始替换，以免替换之前的vis[i-1][?]被换成了vis[i][?]。
状态转移⽅程如下：vis[j]=vis[j-xt[i]]+xw[i],当j>=xt[i];vis[j]=vis[j],当j<xt[i];代码如下：for(int i=1;i<=m;i++)for (int j = t;j >= 1;j--){if (j >= xt[i])vis[j] = max(vis[j - xt[i]] + xw[i], vis[j]);elsevis[j] = vis[j];} ⼜做了⼀个题，其中每种药的个数不限制，这样⼀来⼜要套⼀个循环vis[i][j]=max(vis[i-1][j-n*xt[i]]+n*xw[i],vis[i-1][j])其中n为选择该药的数量。
动态规划（生产和存储问题）一、动态规划法的发展及其研究内容动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。
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)的演变的结果。
四类基本模型1 优化模型1.1 数学规划模型线性规划、整数线性规划、非线性规划、多目标规划、动态规划。
1.2 微分方程组模型阻滞增长模型、SARS 传播模型。
1.3 图论与网络优化问题最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。
1.4 概率模型决策模型、随机存储模型、随机人口模型、报童问题、Markov 链模型。
1.5 组合优化经典问题● 多维背包问题(MKP)背包问题：n 个物品，对物品i ，体积为i w ，背包容量为W 。
如何将尽可能多的物品装入背包。
多维背包问题：n 个物品，对物品i ，价值为i p ，体积为i w ，背包容量为W 。
如何选取物品装入背包，是背包中物品的总价值最大。
多维背包问题在实际中的应用有：资源分配、货物装载和存储分配等问题。
该问题属于NP 难问题。
● 二维指派问题(QAP)工作指派问题：n 个工作可以由n 个工人分别完成。
工人i 完成工作j 的时间为ij d 。
如何安排使总工作时间最小。
二维指派问题（常以机器布局问题为例）：n 台机器要布置在n 个地方，机器i 与k 之间的物流量为ik f ，位置j 与l 之间的距离为jl d ，如何布置使费用最小。
二维指派问题在实际中的应用有：校园建筑物的布局、医院科室的安排、成组技术中加工中心的组成问题等。
● 旅行商问题(TSP)旅行商问题：有n 个城市，城市i 与j 之间的距离为ij d ，找一条经过n 个城市的巡回（每个城市经过且只经过一次，最后回到出发点），使得总路程最小。
● 车辆路径问题(VRP)车辆路径问题（也称车辆计划）：已知n 个客户的位置坐标和货物需求，在可供使用车辆数量及运载能力条件的约束下，每辆车都从起点出发，完成若干客户点的运送任务后再回到起点，要求以最少的车辆数、最小的车辆总行程完成货物的派送任务。
TSP 问题是VRP 问题的特例。
● 车间作业调度问题(JSP)车间调度问题：存在j 个工作和m 台机器，每个工作由一系列操作组成，操作的执行次序遵循严格的串行顺序，在特定的时间每个操作需要一台特定的机器完成，每台机器在同一时刻不能同时完成不同的工作，同一时刻同一工作的各个操作不能并发执行。
动态规划总结——经典问题总结本文着重讨论状态是如何表示，以及方程是怎样表示的。
当然，还附上关键的，有可能作为模板的代码段。
但有的代码的实现是优化版的。
经典问题总结最长上升子序列（LIS）问题描述如下:设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。
求最大的m值。
这里采用的是逆向思维的方法，从最后一个开始想起，即先从A[N]（A数组是存放数据的数组，下同）开始，则只有长度为1的子序列，到A[N-1]时就有两种情况，如果a[n-1] < a[n] 则存在长度为2的不下降子序列a[n-1],a[n]；如果a[n-1] > a[n] 则存在长度为1的不下降子序列a[n-1]或者a[n]。
有了以上的思想，DP方程就呼之欲出了（这里是顺序推的，不是逆序的）：DP[I]=MAX（1,DP[J]+1）J=0,1,...,I-1但这样的想法实现起来是）O(n^2)的。
本题还有更好的解法，就是O(n*logn)。
利用了长升子序列的性质来优化，以下是优化版的代码：//最长不降子序const int SIZE=500001;int data[SIZE];int dp[SIZE];//返回值是最长不降子序列的最大长度,复杂度O(N*logN)int LCS(int n) { //N是DATA数组的长度,下标从1开始int len(1),low,high,mid,i;dp[1]=data[1];for(i=1;i<=n;++i) {low=1;high=len;while( low<=high ) { //二分mid=(low+high)/2;if( data[i]>dp[mid] ) {low=mid+1;}else {high=mid-1;}}dp[low]=data[i];if( low>len ) {++len;}}return len;}最长公共子序列（LCS）给出两个字符串a, b，求它们的最长、连续的公共字串。
动态规划总结1. 按状态类型分写在前面：从状态类型分，并不表示一题只从属于一类。
其实一类只是一种状态的表示方法。
可以好几种方法组合成一个状态，来解决问题。
1.1.编号（长度）动态规划共性总结本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。
一般来说，有两种编号的状态：状态(i)表示前i个元素决策组成的一个状态。
状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。
题库a)最长不下降子序列以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。
于是很容易想到O(n2)得算法。
但本题可合理组织状态，引入一个单调的辅助数组，利用单调性二分查找，优化到O(nlogn)。
关于优化详见优化章。
一些问题可将数据有序化，转化成本题。
应用：拦截导弹(NOIP99 Advance 1) 就是原题。
Beautiful People (sgu199)，要将数据有序化：其中一个权作为第一关键字不下降排列，另一个权作为第二关键字不上升。
Segment (ural 1078)，将线段的左端点有序化就可以了。
b)LCS状态(i,j)，表示第1个字符串的第i位，与第2个字符串的第j位匹配，得到的最长的串。
若有多个串要LCS，则加维，即几个串就几个维。
我也将此题归入路径问题。
c)花店橱窗布置(IOI99)见路径问题。
1.2.区间动态规划共性总结本类问题与下一章的划分问题的决策的分割点无序交集比较大（占本类问题的30%）。
题库a)石子合并见划分问题b)模版匹配(CEOI01,Patten)这题特殊的地方是状态的值是一个集合而不是一个数。
c)不可分解的编码(ACM World Final 2002)d)Electric Path(ural1143)e)邮局(IOI2000 Day2 1)若状态表示的思路从第i个村庄可以从属于哪个邮局，无最优子结构。
转变一个方向：第k个邮局可以“控制”一个区间的村庄[i,j]。
于是方程就显然了:f(k,i,j)=min{f(k-1,p,i-1)+w(i,j)}(k-1<=p<=i-1)S(i) 为村庄i到原点的距离。
w(i,j)=min{k| Sum{|S(k)-S(p)|}(i<=p<=j)}(i<=k<=j) 找到[i,j]间最好的一个邮局点。
不过可以发现Sum{|S(k)-S(p)|是单调的，所以取中位数就可以了。
即上式中k的取值范围只有floor((i+j)/2), ceil((i+j)/2)两个。
Floor是下取整。
Ceil是上取整。
这样每次转移时间降到O(1)。
注意到是区间连续的，即(p,i-1) 和(i, j) 中的i-1, i是连续的，所以空间可以降维：f(i,j)表示放前i个邮局到前j个村庄的最优值。
f(i,j)=min{f(i-1,p-1)+w(p,j)}(i-1<=p<=j-1}e(i,j) 为当f(i,j)到达最优值时的p.通过证明四边形不等式，得到e(i,j)<=e(i,j+1)<=e(i+1,j+1)决策数量又少了一个数量级。
1.1.坐标动态规划共性总结之后的一些问题，状态是由坐标维与其他的维组成。
本类与划分问题(是2维或多维的坐标系的划分)与路径问题的交集占本类问题中大多数。
题库a)棋盘分割(NOI99 4)主要是将公式变形，变形后的公式很容易看出方程。
状态是由2个坐标组成的4元组(x1,y1)(x2,y2)，表示一个子棋盘。
这有点像之前的区间动态规划，只不过是将1维转2维。
后见路径问题。
1.2.数轴动态规划共性总结题库a)01背包应用：装箱问题（NOIP01 Trade 4）就是原题。
值币分割可利用方程的性质，空间降1维。
币值可重复的值币分割(pku1742, Problem F LouTianCheng’s Contest in POJ)使用左右法在定位上加速。
另给状态加一个属性last,记录上一次剩下的可用的同币值硬币数（利用了当前转移是唯一前驱的特点）。
b)取火柴问题(sgu153 Playing with matches)c)Stone Pile(ural1005 Stone Pile)d)公路巡逻(CTSC2000)1.3.5.树型动态规划共性总结1）动态规划的顺序一般按照后序遍历的顺序，即处理完儿子再处理当前节点，才符合树的子结构的性质。
2）多叉树转换为二叉树由于要分配附加维到各个节点，而分配附加维是个划分问题，若还是按当前节点到各个儿子节点分配，则成了一个整数划分问题,O(n2)。
所以要把多叉树转换为二叉树，这样才能按动态规划的方式只决策当前点的分配问题, O(n)。
3）加当前点的选或不选的常数维加此维解决的是后效性问题。
……………………4）在将边信息转成树时的技巧将读入的边分裂成2条边，将这2条边关联起来（就是找到一条边，另一条边的编号就知道）。
用前向星表示法表示边（按起点有序），以后用边的时候，用了一条边打不可用标志，也将关联边打不可用标志。
这样可以保证O(n)的时间完成信息处理，而且在父节点找儿子的过程中带来很大的方便。
5）复杂度树型动态规划复杂度基本上是O(n)；若有附加维m，则是O(nm)。
题库a)选课(CTSC97-3)由于要分配课程数，所以要多叉树转换为二叉树。
b)贪吃的九头龙(NOI02-3)若小头数大于1的话，则让不同的小头吃一段树枝的2个端点。
这样就把问题转化成：附加维是大头吃的个数，当前点由不由大头吃的常数维的动态规划。
由于涉及划分问题，所以要多叉树转换为二叉树。
c)求树的质心(sgu134 Centroid)给出一棵边不带权的树，求点,使得去掉此点后,剩下的最大的连通子图的顶点数最小.d)求树中的点最远距离最近。
给出一棵边带权的树，求树中的点，使得此点到树中的其他结点的最远距离最近。
Computer Network (sgu149)Computer Net (ural1056)1.1.集合动态规划（状态压缩）共性总结1)数据特殊性给出的数据在某一个或几个维度上一般具有比较小的范围（可以枚举一类的状态）。
一个枚举的状态是一个集合。
2)编码由于集合中元素个数的不定性或范围大，直接开数组存，不好索引数组（编程复杂度太高），所以要将集合编码。
利用数据的可枚举性，将枚举的状态(集合)编码。
一般来说码值的范围要很小（尽量排除无用的码值，如炮兵：当前格和上格存在炮兵的情况是非法的，可以排除）。
规定编码的码值代表的意思，要尽量规定好维护的码值。
（如炮兵：当前格存在炮兵的用2，上格存在炮兵用1。
这样下一层的规划时，只要码值-1即可）。
有时候可以直接利用编码的顺序动态规划，因为这时编码已经是拓补有序。
如TSP问题当前已选点集合的状态的前驱的编码的值一定比当前的编码的值小。
3)状态压缩对有限阶段的放置情况，行走情况编码（其实质也是放置的集合或行走路线的集合），这样的编码，也有人谓之：“状态压缩”。
此类题以“炮兵阵地”为典型，进行扩展。
题库a)购物（IOI95-2）可将每种物品按5进制编码。
（5为每种物品数的上限）由于物品数的上限为5，比较小，也可直接开数组存。
b)Roger游戏任务一（CTSC98 Day2 4）一个正方体在一个方格内的状态只有24种，而且可以通过顶面和前面来表示，这样用3维的状态(x,y,p)就可以解决，p为1到24种状态中的一种。
c)TSP问题观察一下TSP的搜索过程：for (x in 未选点) TSP(x)即当前路的最后一个节点为x,现在要选择下一个节点y,而y要在未选点的集合中。
若未选点或已选点的集合已确定，则后效性消除。
可以DP。
状态为令X为当前路的已选点的集合(含i)，当前路的最后一个节点为i。
2元组(X,i)为经过已选点的集合X到节点i的最短长度。
将X编码即可。
注意：并没有因为动态规划将问题从NP类带到P类。
应用: DNA Laboratory(Problem B,TU-Darmstadt Programming Contest 2004)将每个串的交迭部分求出，就可以将问题专成TSP但要输出字典序最小的，则需要注意DP顺序。
有具体的报告。
d)炮兵阵地十分经典，详见报告。
应用:Another Chocolate Maniac(sgu132) 类似炮兵的做法的最值，只不过是求最小值，麻烦点。
Hardwood floor(sgu131) 类似炮兵的做法的统计Little Knights(sgu225) 类似炮兵的做法的统计,数据量太大要constLittle Kings(sgu223) 类似炮兵的做法的统计Bugs公司(CEOI 2002) 类似炮兵的做法的最值1.2.利用动态规划思想求最值，编号（循环变量）的迭代共性总结要利用上次的一些运算“剩下”的循环变量作当前循环的边界，主要在于找出一种决策顺序，使之成立。
题库a)奶牛浴场b)Communication System将数据有序化, 从大到小枚举带宽, 每次可利用上次处理的结果Min, 来决策当前状态。
称作迭代, 或就是一种动态规划。
(zju1409, Problem C Tehran 2002 Iran Nationwide Internet Programming Contest)1.3.记忆化搜索题库Magic Trick (Problem G, TU-Darmstadt Programming Contest 2004)1. 按转移方式分1.1.存在性递推1)01统计(CTSC99 1)2)卡特兰数circle(sgu130)3)鹰蛋1.2.求一系列的分割（合并）点（划分问题）1.2.1.决策的分割点有序共性总结a)有序性每次决策的点的编号是有序的，即要按决策的顺序输出分割点的编号的话，编号是有序的，满足分割点的编号按升序排列。
b)方程一般形式f(n,m)=optimize{f(k,m-1)+w(k+1,n)}(n,m)表示从1到n个点中划分为m个部分的最优值；k为决策的分割点，即第m个部分为k+1到n；这里optimize可以为max,min。
题库a)整数划分常应用在将一个权分配给一定的小分割块，如：将大堆的石子分成一定的小堆，小堆可为空，大堆要分完。
有时应用在树型动态规划（二叉转多叉）中。
b)乘积最大(NOIP00 Advance 2)就是按上面的一般式的方程做。
1.2.2.决策的分割点无序共性总结a)无序性每次决策的点的编号是无序的，即要按决策的递归顺序输出分割点的编号的话，编号是无序的。
b)方程一般形式f(i,j)=optimize{f(i,k-1)+f(k+1,j)}+w(i,j)(i,j)表示从i到j的范围内选取一个分割点k的最优值，子问题是分割点左边(i,k-1)和右边(k+1,j)的点的范围的最优值；这里optimize可以为max,min。
