Generic placeholder image
闲敲代码、落灯花
What's past is prologue

联系邮箱:email@hezehua.net


联系QQ:1907330840

座右铭

保持热情,持续学习,每日精进

动态规划入门之国王的金矿

动态规划入门之国王的金矿

本文与作者在csdn上的博文【动态规划入门之国王的金矿】保持同步


最近学习算法,对动态规划不太了解,使用的时候照搬转移方程式,知其然不知其所以然,今天看到一篇动态规划的教程,解释得非常通俗,原文在这里[动态规划入门教程] (http://blog.csdn.net/woshioosm/article/details/7438834),下面我用自己的记忆和理解讲讲我对动态规划的一点小心得。
首先,动态规划方法适合的题型4个基本特点是:
1、最优子结构,当前一个状态得到最佳解时,当前状态在前一个状态下一定有最佳解;
2、子问题重叠,每个状态下要解决的问题除参数不同外,其本质是一样的;
3、有边界,当解决了最后一个子问题时,整个问题得解;
4、子问题独立,解决一个子问题时不依赖于另一个同级的子问题,只与它的母问题有关;
当存在这四个特点时很大程度上可以确定用动态规划的方法解觉了。
而解决动态规划问题的关键在于写出状态转移方程式,一般来说,对应一个状态下,对某件事情是否执行,这是两个子问题,每个子问题都可以递归下一个状态,最终到达边界条件返回,再判断最开始的状态下两个子问题的最优解,即是整个问题的答案。

我再使用国王的金矿的例子来解释动态规划的实现过程:
有一个国家的国王为了增强国力要开采已探明储量的5座金矿,开采每一座金矿所需的人员是固定的,而且为了能顺利将金矿开采又不耽误人民生活,国王决定只调配500人去挖金矿,要同时开采所有金矿,而且每个人民只开采一次,他要向国会说明开采金矿能带来多少金子,但是问题来了,由于没有足够的人手一次性把所有金矿都开采,怎么搞清能获得最多金子的数量是个难题。

苦思良久,国王有一个好办法了,他想,我只要知道前4座金矿最多能开采多少金子就能计算出开采所有金矿最多能获得多少金子了。他对左丞相说我不开采第5座金矿,你想办法告诉我开采前4座金矿最多能获得多少金子,又对右丞相说我要开采第5座金矿,用掉100个劳力,你想办法告诉我开采前4座金矿最多能获得多少金子。

这下子,国王不急丞相急了,左丞相们想啊, 国王这么聪明,要我告诉他前4座金矿最多能开采多少金子,那我是不是也可以学学国王让大臣告诉我前三座金矿最多能挖多少金子呢,于是左丞相叫来两个大臣,对其中一个说,我要240人用于开采第4、5座金矿,其它人手给你调配的话,你告诉我前三座金矿最多能开采多少金子,又对另一个说我要用100人开采第5座金矿,第4座不开采,其它人手给你调配的话你告诉我前三座金矿最多能挖多少金子。

右丞相焦头烂额之际,打听到左丞相有此妙计,不禁豁然开朗,只要学着国王的做法,把前几座金矿的最大开采量交给属下去解决,我只要决定一座金矿是否开采得出较大值不就得到答案了吗?于是,右丞相也依法炮制,也叫两个大臣,让他们分别在开采与不开采第4座金矿的前提下调查前三座金矿的最大产量。

接下来,这个计算金矿最大开采量的办法被传开了,这个国家的人民,纷纷赞扬国王的聪明,他们把这种办法叫做国王的金矿。

国王的故事果然很生动形象啊,知道i-1座金矿的最大产量就一定能知道i座金矿的最大产量,这是最优子结构,每个人要知道i座金矿的最大产量就必须知道知道i-1座金矿的最大产量,这是子问题重叠,最终当考虑第1座金矿的最大产量时,只要看是否有足够人手开采第1座金矿,有的话,答案是已探明的储量,没有的话就是0,然后答案汇报到上级,上级再得出第2座金矿开采与不开采得出的较大产量,再往上汇报…,这就是边界,而每个人从上级得到的前提都是不同的,上级决定开不开采,再将这个前提之一告诉下属,而下属不需要考虑上级给另一个下属什么前提,这是子问题独立

猜你喜欢
算法--生成1~n的排列
阅读 569

在暴力求解法中,我们常常要用上枚举一些简单内容以便方便获得解,若要输出整数n的前n个整数的全排列,则按字典序输出为: (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)。 从中我们似乎发现了一些规律:先输出以1开头的排列,再输出以2开头的排列,然后是3;...

子集生成算法——增量构造法
阅读 1071

思路是一次选出一个元素放入集合中生成0~n的子集,每次选出最小的值放入集合中,通过从0递增得到下一个位置的值。#include #include #include #include

生成0~n序列的子集对于0~n的每一个值在集合中都有存在和不存在两种状态,所以递归每个值的存在状态即可生成子集#include #include #include #include

乘法运算过程模拟法首先获取输入的乘数(a)与被乘数(b)字符串,按一般乘法运算过程,先是a的最后一位数字与b的最后一位数字相乘,接着a中用于相乘的数下标递减,直到a中所有数字与b最后一位都相乘过,保存结果后再递减b中的用于相乘的数字的下标,循环下去,直到b中每一位数都与a所有数相乘完。 在这个过程...

生成子集——二进制法
阅读 546

用二进制位的0和1表示集合中是否存在该元素要生成0~n的子集,先生成0~n的二进制序列,这些序列的0、1位正好可以对应一个子集中全集在该位置上的元素是否存在,将其作为子集中存在的元素的标记,输出对应元素。#include #include

太残忍,半个月不做题,就对题目毫无感觉了,明明思路正确清晰,但敲的代码满满的bug,连输入字符串前要开辟空间都能无视。。。还在输入后就清空了却在后面一个劲的对它操作。。。略怀悲伤地把代码改好了。#include #include #incl...

算法--八皇后问题
阅读 369

在棋盘上放置8个皇后,使得他们不能相互攻击,此时,每个皇后的攻击范围为同行同列和同对角线,要求找出所有解, 回忆之前分析生成排列所用的解答树,我们再把问题简化为四皇后问题,规则不变,写出它的完整解答树 与生成1~n的排列这篇博文中的解答树最大的不同点就是----只有一条或者几条路径可以...

算法--库函数实现全排列
阅读 396

c++的STL中提供了一个库函数next_permutation,代码如下: #include #include #include #include #include #include using namespace std; int main(){ int n,p[10]; ...