动态规划例子

1、. -有 8 万元的投资可以投给 投资额3 个过目,每个工程在不同筒子数额下以万元为单位的利润如下表盈利0 1 2 3 4 5 6 7 8 工程工程 1 0 5 15 40 80 90 95 98 100 工程 2 0 5 15 40 60 70 73 74 75 工程 3 0 4 26 40 45 50 51 52 53 请支配投资方案,使总的利润最大；写出你所设的状态变量、决策变量、状态转移方程与递推关系式和手工求解的具体步骤及构造；求解：状态变量：xk 表示留给工程 k.n 的投资额,其中 n 为工程总个数, k=1.n. 决策变量： uk 表示投给工程 k 的投资额 . 答应决策集合：

2、状态转移方程：递推关系式：其中,表示工程 k 的投资额为 uk 时的盈利 . 针对此题, n = 3,xk 最大取 8 手工详解过程：1.初始化 k = 3 .word.zl- x3. 0 1 2 3 4 5 6 7 -8 f3x3 0 4 26 40 45 50 51 52 53 2.k = 2 - .word.zlx2. 0 1 2 3 4 5 6 7 -8 f2x2 0 5 26 40 60 70 86 100 110 3.k = 1 x10 1 2 3 4 5 6 7 8 f1x1 0 5 26 40 80 90 106 120 140 最终结果： 给工程 1 投资 4 万元,工程 2

3、 投资 4 万元,工程 3 不投资,将获得最大利润 140万元. python 实现自顶向下,自底向上常用的算法设计思想主要有动态规划、贪婪法、随机化算法、回溯法等等,这些思想有 重叠的局部,当面对一个问题的时候,从这几个思路入手往往都能得到一个仍不错的答案；原来想把动态规划单独拿出来写三篇文章呢,后来发觉自己学疏才浅,实在是只能讲一些皮毛,更深化的东西尝试构思了几次,也没有什么进展,准备每种设计思想就写一篇吧；动态规划 Dynamic Programming是一种特别有用的用来解决复杂问题的算法,它通过把 复杂问题分解为简洁的子问题的方式来获得最优解；一、自顶向下和自底向上总体上来说,我们可

4、以把动态规划的解法分为自顶向下和自底向上两种方式；- .word.zl. -一个问题假如可以使用动态规划来解决,那么它必需具有“ 最优子构造,简洁来说就是,假如该问题可以被分解为多个子问题,并且这些子问题有最优解,那这个问题才可以使用动态规划；自顶向下 Top-Down 自顶向下的方式其实就是使用递归来求解子问题,最终解只需要调用递归式,子问题逐步往 下层递归的求解； 我们可以使用缓存把每次求解出来的子问题缓存起来,下次调用的时候就 不必再递归运算了；举例闻名的斐波那契数列的运算：#./usr/bin/env python # coding:utf-8 deffibnumber: ifnumb

5、er= 0ornumber= 1: return1 else: returnfibnumber-1+fibnumber-2 if_name_= _main_: printfib35 有一点开发经受的人就能看出,fibnumber-1 和 fibnumber-2会导致我们产生大量的重复计算,以上程序执行了 14s 才出结果,现在,我们把每次运算出来的结果储存下来,下一次需 要运算的时候直接取缓存,看看结果：#./usr/bin/env python # coding:utf-8 cache= deffibnumber: - .word.zl. -ifnumberincache: returnca

6、chenumber ifnumber= 0ornumber= 1: return1 else: cachenumber= fibnumber-1+ fibnumber-2 returncachenumber if_name_= _main_: printfib35 消耗时间为 0m0.053s 成效提升特别明显；自底向上 Bottom-Up 自底向上是另一种求解动态规划问题的方法,有可能的结果,往上层逐步累加子问题的解；它不使用递归式, 而是直接使用循环来运算所我们在求解子问题的最优解的同时,也相当于是在求解整个问题的最优解；其中最难的局部是找到求解最终问题的递归关系式,或者说状态转移方程；这

7、里举一个 01 背包问题的例子：你现在想买一大堆算法书,需要许多钱, 所以你准备去抢一个商店,这个商店一共有 n 个商品；问题在于,你只能最多拿 W kg 的东西； wi 和 vi 分别表示第 i 个商品的重量和价值；我们的目标就是在能拿的下的情形下,获得最大价值, 求解哪些物品可以放进背包；对于每一个商品你有两个挑选：拿或者不拿；第一我们要做的就是要找到“ 子问题是什么,我们发觉,每次背包新装进一个物品,就可以把剩余的承重才能作为一个新的背包来求解,始终递推到承重为0 的背包问题：作为一个聪慧的贼,你用 mi,w表示偷到商品的总价值,其中 i 表示一共多少个商品,w 表示总重量,所以求解 m

8、i,w就是我们的子问题,那么你看到某一个商品 i 的时候,如何打算- .word.zl. -是不是要装进背包,有以下几点考虑：1. 该物品的重量大于背包的总重量,不考虑,换下一个商品；2. 该商品的重量小于背包的总重量,那么我们尝试把它装进去,假如装不下就把其他东西换出来,看看装进去后的总价值是不是更高了,否那么仍是依据之前的装法；3.极端情形,全部的物品都装不下或者背包的承重才能为0,那么总价值都是0；由以上的分析,我们可以得出mi,w 的状态转移方程为：有了状态转移方程,那么写起代码来就特别简洁了,第一看一下自顶向下的递归方式,比较简洁懂得：#./usr/bin/env python #

9、coding:utf-8 cache= items=range0,9 weights=10,1,5,9,10,7,3,12,5 values=10,20,30,15,40,6,9,12,18 # 最大承重才能 W=4 defmi,w: ifstri+,+strwincache: returncachestri+,+strw result=0 - .word.zl. -# 特别情形 ifi= 0orw= 0: return0 # w wi ifw= wi ifw= weightsi: # 把第 i 个物品放入背包后的总价值 take_it=mi-1,w-weightsi+valuesi # 不把

10、第 i 个物品放入背包的总价值 ignore_it=mi-1,w # 哪个策略总价值高用哪个 result=maxtake_it,ignore_it iftake_itignore_it: printtake ,i else: printdid not take,i cachestri+,+strw=result returnresult if_name_= _main_: # 背包把全部东西都能装进去做假设开场- .word.zl. -printmlenitems-1,W 改造成非递归,即循环的方式,从底向上求解：#./usr/bin/env python # coding:utf-8 ca

11、che= items=range1,9 weights=10,1,5,9,10,7,3,12,5 values=10,20,30,15,40,6,9,12,18 # 最大承重才能 W=4 defknapsack: forwinrangeW+1: cacheget_key0,w=0 foriinitems: cacheget_keyi,0=0 forwinrangeW+1: ifw= weightsi: ifcacheget_keyi-1,w-weightsi+valuesicacheget_keyi-1,w: cacheget_keyi,w=valuesi+cacheget_keyi-1,w-

12、weightsi else: cacheget_keyi,w=cacheget_keyi-1,w else: - .word.zl. -cacheget_keyi,w=cacheget_keyi-1,w returncacheget_key8,W defget_keyi,w: returnstri+,+strw if_name_= _main_: # 背包把全部东西都能装进去做假设开场 printknapsack 从这里可以看出,其实许多动态规划问题都可以使用循环替代递归求解,他们的区分在于,循环方式会穷举出全部可能用到的数据,而递归只需要运算那些对最终解有帮忙的子问题的 解,但是递归本身是很

13、消耗性能的,所以具体实践中怎么用要看具体问题具体分析；最长公共子序列 LCS解决了 01 背包问题之后,我们对“ 子问题和“ 状态转移方程有了一点点懂得,现在趁 热打铁,来试试解决 LCS 问题：字符串一“ABCDABCD 和字符串二BDCFG 的公共子序列不是公共子串,不需要连续是 BDC ,现在给出两个确定长度的字符串X 和 Y,求他们的最大公共子序列的长度；第一,我们仍是找最优子构造,即把问题分解为子问题,X 和 Y 的最大公共子序列可以分解为 X 的子串 Xi 和 Y 的子串 Yj 的最大公共子序列问题；其次,我们需要考虑 Xi 和 Yj 的最大公共子序列 Ci,j 需要符合什么条件：

14、1. 假如两个串的长度都为 0,那么公共子序列的长度也为 0；2. 假如两个串的长度都大于 0 且最终面一位的字符一样,那么公共子序列的长度是 Ci- 1,j- 1的长度加一；3.假如两个子串的长度都大于0,且最终面一位的字符不同,那么最大公共子序列的长度是 Ci- 1,j和 Ci,j- 1的最大值；- .word.zl. -最终,依据条件获得状态转移函数：由此转移函数,很简洁写出递归代码：#./usr/bin/env python # coding:utf-8 cache= # 为了下面表示便利更简洁懂得,数组从 1 开场编号 # 即当 i,j 为 0 的时候,公共子序列为 0,属于极端情形

15、 A=0,A,B,C,B,D,A,B,E,F B=0,B,D,C,A,B,A,F defCi,j: ifget_keyi,jincache: returncacheget_keyi,j result=0 ifi0andj0: ifAi= Bj: result=Ci-1,j-1+1 else: result=maxCi,j-1,Ci-1,j - .word.zl. -cacheget_keyi,j=result returnresult defget_keyi,j: returnstri+,+strj if_name_= _main_: printClenA-1,lenB-1 上面程序的输出结果

16、为 5,我们也可以像背包问题一样,把上面代码改造成自底向上的求解 方式,这里就省略了；但是实际应用中, 我们可能更需要求最大公共子序列的序列,而不只是序列的长度,所以我们下面额外考虑一下如何输出这个结果；其实输出LCS 字符串也是使用动态规划的方法,我们假设LCSi,j表示长度为i 的字符串和长度为 j 的字符串的最大公共子序列,那么我们有以下状态转移函数：其中 Ci,j是我们之前求得的最大子序列长度的缓存,依据上面的状态转移函数写出递归代 码并不麻烦：#./usr/bin/python # coding:utf-8Dynamic Programming CACHE= # 为了下面表示便利,数

17、组从1 开场编号.word.zl- . 0,属于极端情形-# 即当 i,j 为 0 的时候,公共子序列为A=0,A,B,C,B,D,A,B,E,F B=0,B,D,C,A,B,A,F deflcs_lengthi,j: Calculate max sequence length ifget_keyi,jinCACHE: returnCACHEget_keyi,j result=0 ifi0andj0: ifAi= Bj: result=lcs_lengthi-1,j-1+1 else: result=maxlcs_lengthi,j-1,lcs_lengthi-1,j CACHEget_keyi,j=result returnresult deflcsi,j: backtrack lcs ifi= 0orj= 0: return ifAi= Bj: returnlcsi-1,j-1+Ai else: - .word.zl. -ifCACHEget