Pascal动态规划.ppt

动态规划-入门门篇 Dynamic programming EZOI 多阶段决策过程 多阶段决策过程多阶段决策过程（ multistep decision process ）是指这样一类特殊的 活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一 个阶段都需要做出决策，全部过程的决策是一个决策序列。 动态规划动态规划（dynamic programming ）算法是解决多阶段决策过程最优 化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算 法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。 求解问题的两个重要性质 最优子结构性质最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的 ，我们就称该问题具有最优子结构性质（ 即满足最优化原理 ）。最优子 结构性质为动态规划算法解决问题提供了重要线索。 子问题重叠性质子问题重叠性质：在用递归算法自顶向下对问题进行求解时，每次产 生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划 算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次， 然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子 问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率 。 动态规划与分治、递归、贪心的区别 递归算法递归算法在程序实现上直观容易，但因为子问题被重复计算，且程序背后存在 对栈的操作，速度（计算复杂度一般是指数级的）上劣于动态规划。在递归的过 程中，通过保存子问题的结果，可以减少计算量，同样是空间换时间的思想，称 作memoization算法。 分治法分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求 出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。动态规 划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含 公共的子问题)，它对每个子问题只解一次，并将结果保存起来，避免每次碰到 时都要重复计算。这就是动态规划高效的一个原因。 在贪婪算法贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态 规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问 题是否具有最优子结构性质。 最短路径问题 图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的 连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城 市E，怎样走路程最短，最短路程的长度是多少? 题1 最长不下降子序列 【问题描述】 设有整数序列b1,b2,b3,bm，若存 在i1bj )，那么前I 个数中最大不下降序列便是前j个数中最大不下降序列后添加bi而得。可 见此任务满足最优子结构，可以用动态规划解决。 通过上面的分析可得状态转移方程如下： F(i)=maxF(j)+1 (jbj)and(filen then len:=fi 记录最大值 题2 数塔 如下图所示的数塔，从顶部出发，在每一结点可以选择向左下走或是 向右下走，一直走到底层，要求找出一条路径，使路径上的数的和最大 。数塔层数用n表示，1=n=100。 题2 数塔 贪心法。时间上有保证，但得不到最优解。主要原因是贪心法只 顾眼前利益，不考虑长远利益。 在规定时间内得到正确结果，唯一的方法就是“动态规划”。 下面以示意图表示动态规划的过程：所选路径为：9-12-10-18-10 注意分析时，有以下几个特点： （1）将问题划分成了4个阶段； （2）每个阶段均得到了“部分”的最优解，得到最优解时，需要进行条件判断 ； （3）从最下面一层往顶层推导。 题3 棋盘路径问题 【题目简介】 有一个n*m的棋盘，左下角为（1,1），右上角为（n,m），如下图： 有一颗棋子，初始位置在（1,1），该棋子只能向右走或者向上走，问 该棋子从（1,1）到（n,m）一共有几条路径？ 输入：两个整数n和m 输出：一个数，路径总数 题3 棋盘路径问题 【题目简介】 如果使用枚举的方法，必定有很多路径被重复走过，这样，势必造成 程序运行时间的浪费，当n和m的值比较大的时候，程序很可能超时。为 了避免程序的重复运行，我们可以通过记录点（1,1）到任意一个点（I,j ）的路径总数来解决这个问题。假设FI,j是点(1,1)到点(I,j)(1in, 1jm)的路径总数，因为棋子在棋盘中只能向右或者向上走，所以棋盘 中只能2个点的棋子可以走到点（I,j），即点(I,j-1)和(i-1,j)，这样，我们 就可以知道，FI,j必定是FI,j-1和Fi-1,j的和，即 Fi,j=Fi-1,j+Fi,j-1 【例4】街道问题 在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方 走。 【例4】街道问题 在一般情况下，如果我们用二维数组H(i，j)和V(i，j)分别表示水平方 向和竖直方向的各路段长度，如H(1，2)表示水平方向上路口 (1，1)到路 口(1，2)的路段长度，V(1，2)表示竖值方向上路口(0，2)到路口(1，2) 的路段长度，则有公式：如 dpl(i，j)=mindpl(i-1，j)+v(i，j)，dpl(i，j-1)+h(i，j) 题5 机器分配 【问题描述】 总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若 获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备 才能使国家得到的盈利最大？求出最大盈利值。其中M15，N10。分 配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备 数M。保存数据的文件名从键盘输入。 数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二 个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台 机器的盈利。 题5 机器分配 【分析】 这是一个典型的动态规划试题。用机器 数来做状态，数组FI，J表示前I个公司分配J 台机器的最大盈利。则状态转移方程为 Fi，j=MaxFi-1，k + Valuei，j-k （0=K=J 题6 0-1背包问题 【题目】 有N件物品和一个容量为V的背包。第i 件物品的费用是ci，价值是wi。求解将哪些 物品装入背包可使价值总和最大。 题6 0-1背包问题 这是最基础的背包问题，特点是：每种物品 仅有一件，可以选择放或不放。 用子问题定义状态：即fiv表示前i件物品 恰放入一个容量为v的背包可以获得的最大价 值。则其状态转移方程便是： fiv=maxfi-1v,fi-1v-ci+wi 题7 完全背包问题 【题目】 有N种物品和一个容量为V的背包，每种物 品都有无限件可用。第i种物品的费用是ci， 价值是wi。求解将哪些物品装入背包可使这 些物品的费用总和不超过背包容量，且价值 总和最大。 题7 完全背包问题 【基本思路】 这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也 就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而 是有取0件、取1件、取2件等很多种。如果仍然按照解01背包时的 思路，令fiv表示前i种物品恰放入一个容量为v的背包的最大权值。仍 然可以按照每种物品不同的策略写出状态转移方程，像这样： fiv=maxfi-1v-k*ci+k*wi 0=k*ci=v 题8 拦截导弹 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截 系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮 弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还 在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数） ，计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度 。 样例： INPUT 389 207 155 300 299 170 158 65 OUTPUT 6 （最多能拦截的导弹数） ， 题8 拦截导弹 【分析】 设 D(i) 为第 i 枚导弹被拦截之后，这套系统最多还能拦截的导弹数（包含被拦 截的第 i 枚）。我们可以设想，当系统拦截了第 k 枚导弹 x k ，而 x k 又是序列 X=x 1 ,x 2 ,x n 中的最小值，即第 k 枚导弹为所有飞来的导弹中高度最低的 ，则有 D(k)=1 ；当系统拦截了最后一枚导弹 xn ，那么，系统最多也只能拦截这 一枚导弹了，即 D(n)=1 ；其它情况下，也应该有 D(i)1 。根据以上分