子集型动态规划讲稿
需积分: 6 84 浏览量
2016-07-30
16:58:29
上传
评论
收藏 135KB PDF 举报
高 2018 级信息学竞赛培训资料
第 1 页
子集型动态规划
一、动态规划概述
最优化问题是信息学竞赛的一大类题目，动态规划是解决这类问题的有力武器，但很多人在尝试理解
并运用它时遇到极大的困难！当你学习了足够多的动态规划例题的时候，你会觉得它跟变魔术一样。在这
里，我们先回顾回溯算法、贪心算法、递推算法分析问题的步骤：
回溯算法 贪心算法 递推算法
1、分步：
2、每步选择：
盲目穷举所有选举择。
3、求解
1、分步
2、每步选择：
用目前看起来最好的选择
（贪心策略）让选择变的唯一
3、构造最优解答
1、分步
2、每步选择：
每种选择就是一类，从而可以使用加法原理
或乘法原理。
3、设置状态函数，写出当前步下的递推方程
（利用加法原理或乘法原理）
从上面看出，分步决策是信息学竞赛分析问题的基本方法——利用前一步（也称为子问题）的解，一步
一步地得到最终的解。分治算法更是体现了这个思想——每一步把问题平分成规模较小的子问题，在解决子
问题后，合并子问题的解从而解决了大问题。
回溯算法作为信息学解题的通用方法，其效率低的原因是需要盲目地穷举所有情况，但在回溯的过程
中就可能有很多状态被重复计算，因此在计算方案数或最优化问题的时候，往往可以用一个状态记忆表来
记忆已经计算过的状态，从而避免重复计算，提高效率！
所以，动态规划实质就是记忆化搜索，是一种高效地实现回溯算法的方法，它的核心是用一个状态记
忆表来记住所有中间状态的结果。因此我们要运用动态规划，首先需要发现朴素的回溯算法递归地一而再、
再而三地计算一些相同的子问题，接下来需要把答案放在记忆表中而不重复计算。
因此动态规划可以采用记忆化搜索，但记忆化搜索有其缺点，比如要用递归，不能优化空间。所以填
表法作为动态规划实现的一种优化方法而广泛使用。下面我们来以实际例子逐步深入地理解动态规划！
二、动态规划举例
例 1、贴邮票[版本 3]（P1394）
问题 1：有 N 种不同面额的邮票，每种只有 1 张。问：可以选用多少张邮票贴出面额 K ？计算并
输出需要邮票数目的最小值和最大值。
问题 2：有 N 种不同面额的邮票，每种只有 p[i] 张。问：可以选用多少张邮票贴出面额 K ？计
算并输出需要邮票数目的最小值和最大值。
问题 3：有 N 种不同面额的邮票，每种邮票有无限多张。问：可以选用多少张邮票贴出面额 K ？计
算并输出需要邮票数目的最小值
和最大值。
【输出】
三行，分别对应问题 1、问题 2、问题 3，如果无解则输出”No answer.”。
【样例】
5 12
1 2 3 6 4
1 2 1 2 1
3 4
2 5
2 12
【数据范围】
1 <= N <= 100; 1 <= K <= 20000; 每种邮票面额不超过 200。
资源评论
