[社会学]2007动态规划2.pptVIP

ACM暑期集训讲座 动态规划（二） ：常见模型 主讲 wangfangbob 自我介绍 wangfangbob 汪方 南开大学数学学院 基础数学专业 描述集合论方向 06级硕士 xiaofangbob@163.com 动态规划的目的 1 重叠子问题： 递归求解时，会出现递归的分枝相互重合，从而造成重复计算，如果计算一次就保存结果就会大量减少计算次数 2 多阶段决策，求解最优值： 求解最优值，往往演变成多个阶段的决策，而决策的数目会随着阶段数量的增长指数增长，利用动态规划的方法可以限制决策数目的增长，提高效率。 一些模型：1.有哪些信誉好的足球投注网站，限制，递推，增维 实例1 给定一个具有N层的数字三角形，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。 典型的多阶段决策 暴力解法： 每一层就是一个决策的阶段，我们遍历有哪些信誉好的足球投注网站所有的方案，然后找出最优解。 第一层只有顶点，决策数1，顺着顶点有两个方向可以选择，决策数2………….. 这样每一层的每一决策到下一层都有2个方向，这样决策数量翻倍，指数增长！ 改为递推，用一元组D(X)描述问题，D(X)表示从顶层到达第X层的最小路径得分。因此，此问题就是求出D(N)(若需要，还应求出最优路径)。这是一种很自然的想法和表示方法。但是很可惜： D(x) - D(x+1) 不成立！ 于是我们思考，可不可以记录多个值，每个阶段不是一个值，而是多个值，从一个阶段的多个值推出下一个阶段的多个值？ 表示法二： 增加一维， 用二元组D(X,y)描述问题，D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。 显然到达y点的路径只能来自于上一层的y-1点或者y点，所以： D(X,y)＝min{D(X-1,y)，D(X-1,y-1)}+a(X,y) D(1,1)＝a(1,1) 我们需要的最终需要的解就是: min{D(N,k)} 1= k = N 。 问题解决！ 思考： 从有哪些信誉好的足球投注网站的角度可不可以得到相同的结论呢？ 暴力有哪些信誉好的足球投注网站算法的弊端就是指数级别的增长 如果能够找到一个非指数增长的量限制其增长，貌似也是可行的 在某一个阶段，也许决策的数量很多，对于本题就是路径数目，但是路径到达的终点都是本层的点，而本层的点是有限，呈线形增长 而且路径对后面决策的影响都是通过这些点 所以有相同终点的路径我们当然选得分最小的那条，而舍弃其他的路径，实际上对于本题我们不需要记录选择了哪一条路径，只需要记录最小得分即可，如果题目要求输出路径，再记录选择的路径。 回顾刚才的状态转移方程： D(X,y)＝min{D(X-1,y)，D(X-1,y-1)}+a(X,y) D(1,1)＝a(1,1) y就是用来限制决策数量的增长。 如果这个题过于简单，还不能完全表达寻找变量来限制决策数量的增长，那么我们来看下一个例题： nkoj1705: [NKPC3]计算机硬件评分系统 小C听说微软新推出的一款操作系统Windows Vista可以对电脑的配置进行评分，很感兴趣。由于小C对硬件软件方面都很了解，就通过一系列的市场调查与实践，制作了一款自己的计算机硬件评分系统。此系统可以对CPU、内存、硬盘、主板、显卡五部分分别进行评分，分数为不超过100的正整数，并以这五个分数中的最低分作为对计算机的总体评分。　　同寝室的小D打算最近购置一台新电脑，他请小C给他当参谋，小C就提供了一些当前的CPU、内存、硬盘、主板、显卡五种硬件的品牌、价格以及每个硬件由他所制作的系统所评价出来的分数。小D准备至多用N元来购买这五种硬件并且他还希望能够得到一台电脑有尽量高的总体评分。　　作为寝室长的你主动要写一个程序来帮助小D购买电脑。 N = 50000，每一种硬件有30000种。 此题决策明显是分5个阶段：每个硬件的决策一个阶段。 暴力有哪些信誉好的足球投注网站的复杂度：30000^5！ 有什么量可以限制决策数量呢？ 我们发现虽然价钱范围不小，硬件数量也很大，但是分数值却只有100个！ 无论到哪个阶段相同分数的决策我们肯定选择钱最少的那种决策。 于是每个阶段的决策数都被限制在了100个。 状态表示： D [ i ][ j ]表示决策到第i个硬件得到分数 j 需要的最小钱数。 a[k]表示第k个这种硬件的得分 b[k]表示第k个这种硬件的价钱 对于每一个得分 j , 我们都把它和30000个硬件配一下： If( j a[k] ) D[ i + 1 ][a[k]] ?= D[ i ][ j ] + b[k] else D[ i + 1 ][ j ] ?= D[ i ][ j ] + b[k] 这样每个j都循环30000次,而j有100个变化,会产生100 * 30000个分枝,但是D[