注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

动态规划的基础内容(DP)  

2015-08-03 11:30:06|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
动态规划链接:http://baike.haosou.com/doc/6995222-7218096.html
        动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法--动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。
        下面举一个例子,证明动态规划的强大,就是探索数字迷塔。

 【问题描述】
  晶晶最近迷上了数字迷宫游戏,整天沉浸在一串串看似简单的数字中自得其乐。数字迷宫游戏的魅力体现在变化中隐含着不变的规律,归纳是探究数字迷宫的法宝之一。例如图10.1-1就是一个由线连接起来的数字小方格组成的数字迷塔。
  这个迷塔共n层,它由n×(n+1)/2个小方格组成。每个小方格中都有一个数字,并且连着下一层的两个小方格。现从塔顶走到塔底,每一步只能走到相邻的方格中,则经过方格的数字之和最大值是多少?这个问题晶晶已经琢磨一天了,她感觉异常棘手,你能帮帮她吗?
【输入格式】
  输入数据共n+1行,第一行是一个整数n(1≤n≤1000),表示数字迷塔的高度,接下来用n行数字表示数字迷塔,其中第i行有i个正整数,且所有的正整数均不大于100。
【输出格式】
  输出数据仅一行。输出可能得到的最大和。
【输入样例】


12 15 
10  6  8 
2  18  9  5 
19  7  10 4 16 
【输出样例】
59
样例说明:9→12→10→18→10 
动态规划的基础内容(DP) - 杨鸿飞 - 一个叫杨鸿飞的人的博客
        这一题,不知道动态规划的人乍一看,还真看不出什么规律,看看贪心行不行,从塔顶开始,可以走12和15这两条路,根据贪心思路,选15,15再选8,8再选9,9再选10,结果是51,少了,为什么?因为贪心目光短浅,只顾眼前利益。然后,就只能乖乖搜索了,可是数据范围,呃……O(2^1000)boooooooow!!!!!!这时,就轮到动态规划上场了!
        先介绍动态规划的核心:阶段,最优,子问题,边界。就是把题目分成几个阶段,每个阶段都有若干个子问题,把每个子问题的解通过最优策略算出来,这样就完成了这个阶段,还要注意边界。注意,根据江老师讲的,阶段的作用是把子问题划分成几个次序,先求几个子问题,通过这几个求过的子问题,可以再求几个新的子问题。有点像递推。
        这题是把每一层看成一个阶段,把“每层的每一个数怎么走和最大”看成子问题,它的最优决策等于它走左边的数怎么走的最大和,它走右边的数怎么走的最大和两个数的最大值加上自己所在格子的数,边界情况是“如果在底层,最大值就是自己所在格子的数”,转移成方程是f[i][j]=max(f[i-1][j+1],f[i-1][j])+a[i][j]。详见程序:
#include<cstdio>
#include<algorithm>

using namespace std;

int a[1010][1010],f[1010][1010];

int main()
{
int n;
/*==========================================读入============================================*/
scanf("%d",&n);
for (int i=1; i<=n; i++)
 for (int j=1; j<=i; j++)
   scanf("%d",&a[i][j]);
/*==========================================初始化==========================================*/
for (int j=1; j<=n; j++) f[n][j]=a[n][j];
/*==========================================处理============================================*/
for (int i=n-1; i>0; i--)    //第i阶段(第i层)
 for (int j=1; j<=i; j++)   //第j个子问题(第i个数)
   f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];  //最优决策
/*==========================================输出===========================================*/
printf("%d",f[1][1]);
}
这十分简单吧!
 动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。

举例:

线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等;

区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等;

树形动规:贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等;

背包问题:01背包问题,完全背包问题,分组背包问题,二维背包,装箱问题,挤牛奶(同济ACM第1132题)等;

动态规划有很多术语,看链接吧,不讲了!

  评论这张
 
阅读(20)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018