动态规划

与贪心算法求局部最优解相比，动态规划求的是全局最优解（但不是每个问题都有最优解，比如NP完全问题就没有最优解） 例： 背包问题之动态规划解决 问题描述： 现在有一个背包可以装4磅物品，现在要从商城里拿尽可能价值高的物品装进包里。 商城物品情况如下 每个动态规划都从一个网格（如下）开始 现在一行一行地填充该网格。 每个格子的计算公式： 填充吉他行 目前最大价值1500（吉他） 填充音箱：目前最大价值3000（音箱） 填充笔记本：目前最大价值3500（吉他+笔记本） 动态规划的原则就是将大问题拆解成多个小问题，先把小问题的最优解求出，再在考虑小问题最优解的前提下，得出最终问题的最优解 本例的背包问题中，先求出只有吉他一种物品时的最优解，再逐步添加物品，最终求出最优解 关于网格计算公式的补充： 整个动态规划求解过程中，是从小问题层逐步求解到大问题，自然每个格子要考虑的第一点就是前一格子的最大值，又，新的一层添加了新物品，所有也要考虑新物品的价值+剩余可用磅数的最大价值（上一层求得） 背包问题补充： 若再添加一个物品 ——项链{‘价值’：1000$，‘重量’：0.5磅} 此时如果沿用之前的网格 如果要装的物品为燕麦，木豆，大米 这种可以一部分一部分取出的物品 动态规划则解决不了这种情形，贪心可以。 旅游行程问题 当然我们可以用动态规划的网格法来得到一条最有价值的旅游路线 如果加入以下景点 在去巴黎的景点所花费的时间中，有0.5天是从伦敦前往巴黎的时间。 因此如果先去了埃菲尔铁塔,则去巴黎的剩下两个景点的花费时间也要减少2个小时 这种情况就不能使用之前的动态规划算法。 动态算法处理的每个子问题都是离散的 再来看一个案例 假如你要经营一个网站，网站主要任务是：英文单词翻译。即用户输入英文单词，你给出相应的翻译。 例用户输入fish，网站输出鱼 如果用户输入的hish，但词典中并没有该单词，此时应给出相似词。 怎么样才算是相似词呢？判断最大子串长度？ 利用动态规划求出两字符串（fish和hish）的最大字串长度 动态规划解决问题总是要先知道网格中的各个元素： 两个坐标轴是什么？网格中的值是什么（通常为要 优化的指标 ） 1，分解问题：要求fish和hish的最大子串，可以先求其字串的最大公共子串（如先求fis和his）。考虑两个坐标轴为两个单词，则网格中的值为最大子串的长度。 接下来填充该网格。不断验证得到单元格公式： 单元格公式解释： 1）两字母相同，则局部最大字串要延长，即斜上方（cell[i][j]）的值加一(这里指标值在斜方向上累加) 2）若是不同，则局部最大字串为0 两字符串的最大字串长度即为网格中的最大值3。 如果用户输入fosh，那么要返回fish还是fort呢？ 如果判断依据为最大子串，则会返回fort，但实际上fish和fosh更像！ 因此我们考虑判断依据为两字符串的最大公共子序列长度（即两字符串公共字符的个数） 求最大公共子序列的单元格公式为： fosh和fort的最大公共子序列长度为2 fosh和fish的最大公共子序列长度为3 此时就可以返回正确结果fish而非fort。 1，动态规划通常用于解决 在给定约束条件下优化某个指标值 2，动态规划的原则就是：将大问题分解成小问题，在解决了小问题的条件下，逐步求解大问题。（一个分解问题的方法就是，将条件逐渐减少，从最简单的情况开始分析） 3，动态规划使用的一个必要条件为： 分解出来的每个小问题都是离散的 4，每种动态规划方案都设计网格 4.1，网格的每个格子都是一个小问题 4.2，网格的每个格子的值都是指标的值 4.3，单元格计算公式需要 具体问题具体分析 。

有N件物品和一个容积为M的背包。第i件物品的体积w[i] ，价值是d[i]。求解将哪些物品装入背包可使价值总和 最大。每种物品只有一件，可以选择放或者不放 (N<=3500,M <= 13000)

我们设V[i][j]表示前i个物品，体积不超过j，取得的最大价值。于是：

但是，这个题目如果这么开二维数组的话，就会超内存，我们得想一种更节省内存的办法。
即考虑：对这些物品而言，不超过j能达到的最大价值，我们设成MaxV[j]。动态规划，要求无后效性，而对前i种物品考虑的取舍，对i种以后的物品取舍，有无后效性（对比，三角形那的滚动数组）

神奇的口袋(百练2755)

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。
John现在有n(1≤n ≤ 20)个想要得到的物品，每个物品的体积分别是a1，a2......an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式
  这道题有两种解法，一种是传统的递归式解法，另外一种是可达型动态规划，设计更加巧妙一些，当作练习题。【Tips:一维动规】
  我们设Ways[i][j]表示用前j件物品凑出i体积的方法数，而题目要求我们求的就是Ways[40][N],那么：

动态规划的基本步骤是划分阶段和选择状态、确定决策并写出状态转移方程和写出规划方程（包括边界条件）。 1、划分阶段和选择状态： 按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 2、确定决策并写出状态转移方程和写出规划方程（包括边界条件）： 决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。 但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。 动态规划的特点： 1、最优化原理（最优子结构性质）： 最优化原理可这样阐述，一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。 2、无后效性： 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。 3、子问题的重叠性： 动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。

动态规划方法的步骤可以总结为：逆序求解（最优目标函数），顺序求（最优策略）、（最优路线）和（最优目标函数值）。 动态规划是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。 意义： 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策（采取措施），一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。 每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。 局限性： 动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。

1.阶段 阶段是指研究的事物在发展过程中所处的时段或地段。处理多阶段决策问题，需要将全过程划分若干阶段，每个阶段进行一次抉择。若演变过程是离散的，则用序列编号i=1，2，…，n表示，称为阶段变量。它可以是空间，也可以是时间。若为时间，则按相等增量Δt离散，或按连续变化，以变量t表示。 2.状态 在多阶段决策过程中，各阶段演变可能发生的情况，称为状态。描述状态的变量称为状态变量。一个阶段可能有若干个状态。若第i阶段有m个状态变量，可用si表示该阶段的状态集合： 华北煤田排水供水环保结合优化管理 3.决策 决策是某阶段状态给定之后，从该状态演变到下一阶段某状态的选择。当阶段的初始状态给定后，做出某一决策，则本阶段的初始状态就变成该阶段的末状态，做出不同的决策，就得出不同的末状态。描述决策变化的量，称为决策变量。常用di（si）表示第i阶段状态处于si时的决策。在实际问题中，决策变量的取值往往被限制在某一范围之内，此范围称为允许决策集合或决策空间，常用di（si）∈Di（si）表示。 4.策略 策略是指一个决策序列。由第1阶段开始至终点为止的过程，称为问题的全过程；由每个阶段的决策di（si）（i=1，2，…，n）所组成的决策序列，称为全过程策略，简称策略，记为P1n。 则 华北煤田排水供水环保结合优化管理 从k阶段开始至终点的过程，称为原问题的后子过程（或称k子过程），其决策序列称为k子过程策略，简称子策略，即 华北煤田排水供水环保结合优化管理 在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合，以P表示。从允许策略范围集合中，找出达到最优效果的策略，称为最优策略，最优策略相应的状态序列，称为最优轨迹。 5.状态转移方程 下一阶段状态Sk+1是本阶段状态变量Sk和决策变量Xk（Sk）的函数，即对于状态Sk的决策结果是Sk+1，记为 华北煤田排水供水环保结合优化管理 简写为 华北煤田排水供水环保结合优化管理 这种从某状态出发到下一阶段某状态的转移规律称为状态转移方程。 6.目标函数 在多阶段最优决策过程中，目标函数是用来衡量策略优劣的数量指标。 状态的转移就产生费用（效益）的改变，它们是同时发生的。设ri表示i阶段的费用（效益），则ri也是si及di的函数，可写为 华北煤田排水供水环保结合优化管理 此式称为第i阶段的费用（效益）方程。若从过程的第一阶段初始状态开始，经历全部阶段，可得到全过程的总费用R，即总费用R是各阶段费用ri的总和，表示为 华北煤田排水供水环保结合优化管理 因为状态和决策往往是一个向量，所以总费用R也是一个向量，其最优值的数量指标，就是过程的目标函数，常用R*表示，即 华北煤田排水供水环保结合优化管理 式中：Opt（optimization）表示最优值，可取极大或极小，依目标性质而定。 通过以上讨论，可将多阶段决策过程归纳为如图3-1所示。 图3-1 多阶段决策过程示意图