动态规划例子.doc

有8万元的投资可以投给3个过目，每个项目在不同筒子数额下（以万元为单位）的利润如下表投资额盈利项目012345678项目105154080909598100项目20515406070737475项目30426404550515253请安排投资计划，使总的利润最大。写出你所设的状态变量、决策变量、状态转移方程与递推关系式和手工求解的详细步骤及结构。求解：状态变量：xk 表示留给项目k.n的投资额，其中n为项目总个数，k=1.n.决策变量：uk 表示投给项目k的投资额.允许决策集合：Dkxk=uk | 0ukxk状态转移方程：xk+1=xk-uk递推关系式：fkxk=ukDkxkmax gkuk+fk+1xk-uk k=n-1,1fnxn=gnxn 其中，gkuk表示项目k的投资额为uk时的盈利.针对本题，n = 3，xk最大取8手工详解过程：1. 初始化k = 3f30=0;f31=4;f32=26;f33=40;f34=45;f35=50;f36=51;f37=52;f38=53. x3012345678f3(x3)04264045505152532. k = 2f20=maxg20+f30=0+0=0;f21=maxg20+f31,g21+f30=max0+4,5+0=5;f22=maxg20+f32,g21+f31,g22+f30=max0+26,5+4,15+0=26;f23=maxg20+f33,g21+f32,g22+f31,g23+f30=max0+40,5+26,15+4,40+0=40;f24=maxg20+f34,g21+f33,g22+f32,g23+f31,g24+f30=max0+45,5+40,15+26,40+4,60+0=60;f25=maxg20+f35,g21+f34,g22+f33,g23+f32,g24+f31,g25+f30=max0+50,5+45,15+40,40+26,60+4,70+0=70;f26=maxg20+f36,g21+f35,g22+f34,g23+f33,g24+f32,g25+f31,g26+f30=max0+51,5+50,15+45,40+40,60+26,70+4,73+0=86;f27=maxg20+f37,g21+f36,g22+f35,g23+f34,g24+f33,g25+f32,g26+f31,g27+f30=max0+52,5+51,15+50,40+45,60+40,70+26,73+4,74+0=100;f28=maxg20+f38,g21+f37,g22+f36,g23+f35,g24+f34,g25+f33,g26+f32,g27+f31,g28+f30=max0+53,5+52,15+51,40+50,60+45,70+40,73+26,74+4,75+0=110.x2012345678f2(x2)0526406070861001103. k = 1f18=maxg10+f28,g11+f27,g12+f26,g13+f25,g14+f24,g15+f23,g16+f22,g17+f21,g18+f20=max0+110,5+100,15+86,40+70,80+60,90+40,95+26,98+5,100+0=140x1012345678f1(x1)0526408090106120140最终结果：给项目1投资4万元，项目2投资4万元，项目3不投资，将获得最大利润140万元.python实现自顶向下，自底向上常用的算法设计思想主要有动态规划、贪婪法、随机化算法、回溯法等等，这些思想有重叠的部分，当面对一个问题的时候，从这几个思路入手往往都能得到一个还不错的答案。本来想把动态规划单独拿出来写三篇文章呢，后来发现自己学疏才浅，实在是只能讲一些皮毛，更深入的东西尝试构思了几次，也没有什么进展，打算每种设计思想就写一篇吧。动态规划（Dynamic Programming）是一种非常有用的用来解决复杂问题的算法，它通过把复杂问题分解为简单的子问题的方式来获得最优解。一、自顶向下和自底向上总体上来说，我们可以把动态规划的解法分为自顶向下和自底向上两种方式。一个问题如果可以使用动态规划来解决，那么它必须具有“最优子结构”，简单来说就是，如果该问题可以被分解为多个子问题，并且这些子问题有最优解，那这个问题才可以使用动态规划。自顶向下（Top-Down）自顶向下的方式其实就是使用递归来求解子问题，最终解只需要调用递归式，子问题逐步往下层递归的求解。我们可以使用缓存把每次求解出来的子问题缓存起来，下次调用的时候就不必再递归计算了。举例著名的斐波那契数列的计算：#!/usr/bin/env python# coding:utf-8def fib(number): if number = 0 or number = 1: return 1 else: return fib(number - 1) + fib(number - 2)if _name_ = _main_: print fib(35)有一点开发经验的人就能看出，fib(number-1)和fib(number-2)会导致我们产生大量的重复计算，以上程序执行了14s才出结果，现在，我们把每次计算出来的结果保存下来，下一次需要计算的时候直接取缓存，看看结果：#!/usr/bin/env python# coding:utf-8cache = def fib(number): if number in cache: return cachenumber if number = 0 or number = 1: return 1 else: cachenumber = fib(number - 1) + fib(number - 2) return cachenumberif _name_ = _main_: print fib(35)耗费时间为 0m0.053s 效果提升非常明显。自底向上（Bottom-Up）自底向上是另一种求解动态规划问题的方法，它不使用递归式，而是直接使用循环来计算所有可能的结果，往上层逐渐累加子问题的解。我们在求解子问题的最优解的同时，也相当于是在求解整个问题的最优解。其中最难的部分是找到求解最终问题的递归关系式，或者说状态转移方程。这里举一个01背包问题的例子：你现在想买一大堆算法书，需要很多钱，所以你打算去抢一个商店，这个商店一共有n个商品。问题在于，你只能最多拿 W kg 的东西。wi和vi分别表示第i个商品的重量和价值。我们的目标就是在能拿的下的情况下，获得最大价值，求解哪些物品可以放进背包。对于每一个商品你有两个选择：拿或者不拿。首先我们要做的就是要找到“子问题”是什么，我们发现，每次背包新装进一个物品，就可以把剩余的承重能力作为一个新的背包来求解，一直递推到承重为0的背包问题：作为一个聪明的贼，你用mi,w表示偷到商品的总价值，其中i表示一共多少个商品，w表示总重量，所以求解mi,w就是我们的子问题，那么你看到某一个商品i的时候，如何决定是不是要装进背包，有以下几点考虑：1. 该物品的重量大于背包的总重量，不考虑，换下一个商品；2. 该商品的重量小于背包的总重量，那么我们尝试把它装进去，如果装不下就把其他东西换出来，看看装进去后的总价值是不是更高了，否则还是按照之前的装法；3. 极端情况，所有的物品都装不下或者背包的承重能力为0，那么总价值都是0；由以上的分析，我们可以得出mi,w的状态转移方程为：有了状态转移方程，那么写起代码来就非常简单了，首先看一下自顶向下的递归方式，比较容易理解：#!/usr/bin/env python# coding:utf-8cache = items = range(0,9)weights = 10,1,5,9,10,7,3,12,5values = 10,20,30,15,40,6,9,12,18# 最大承重能力W = 4def m(i,w): if str(i)+,+str(w) in cache: return cachestr(i)+,+str(w) result = 0 # 特殊情况 if i = 0 or w = 0: return 0 # w wi if w = wi if w = weightsi: # 把第i个物品放入背包后的总价值 take_it = m(i-1,w - weightsi) + valuesi # 不把第i个物品放入背包的总价值 ignore_it = m(i-1,w) # 哪个策略总价值高用哪个 result = max(take_it,ignore_it) if take_it ignore_it: print take ,i else: print did not take,i cachestr(i)+,+str(w) = result return resultif _name_ = _main_: # 背包把所有东西都能装进去做假设开始 print m(len(items)-1,W)改造成非递归，即循环的方式，从底向上求解：#!/usr/bin/env python# coding:utf-8cache = items = range(1,9)weights = 10,1,5,9,10,7,3,12,5values = 10,20,30,15,40,6,9,12,18# 最大承重能力W = 4def knapsack(): for w in range(W+1): cacheget_key(0,w) = 0 for i in items: cacheget_key(i,0) = 0 for w in range(W+1): if w = weightsi: if cacheget_key(i-1,w-weightsi) + valuesi cacheget_key(i-1,w): cacheget_key(i,w) = valuesi + cacheget_key(i-1,w-weightsi) else: cacheget_key(i,w) = cacheget_key(i-1,w) else: cacheget_key(i,w) = cacheget_key(i-1,w) return cacheget_key(8,W)def get_key(i,w): return str(i)+,+str(w)if _name_ = _main_: # 背包把所有东西都能装进去做假设开始 print knapsack()从这里可以看出，其实很多动态规划问题都可以使用循环替代递归求解，他们的区别在于，循环方式会穷举出所有可能用到的数据，而递归只需要计算那些对最终解有帮助的子问题的解，但是递归本身是很耗费性能的，所以具体实践中怎么用要看具体问题具体分析。最长公共子序列（LCS）解决了01背包问题之后，我们对“子问题”和“状态转移方程”有了一点点理解，现在趁热打铁，来试试解决LCS问题：字符串一“ABCDABCD”和字符串二”BDCFG”的公共子序列（不是公共子串，不需要连续）是BDC，现在给出两个确定长度的字符串X和Y，求他们的最大公共子序列的长度。首先，我们还是找最优子结构，即把问题分解为子问题，X和Y的最大公共子序列可以分解为X的子串Xi和Y的子串Yj的最大公共子序列问题。其次，我们需要考虑Xi和Yj的最大公共子序列Ci,j需要符合什么条件：1. 如果两个串的长度都为0，则公共子序列的长度也为0；2. 如果两个串的长度都大于0且最后面一位的字符相同，则公共子序列的长度是Ci1,j1的长度加一；3. 如果两个子串的长度都大于0，且最后面一位的字符不同，则最大公共子序列的长度是Ci1,j和Ci,j1的最大值；最后，根据条件获得状态转移函数：由此转移函数，很容易写出递归代码：#!/usr/bin/env python# coding:utf-8cache = # 为了下面表示方便更容易理解，数组从1开始编号# 即当i,j为0的时候，公共子序列为0，属于极端情况A = 0,A,B,C,B,D,A,B,E,FB = 0,B,D,C,A,B,A,Fdef C(i,j): if get_key(i,j) in cache: return cacheget_key(i,j) result = 0 if i 0 and j 0: if Ai = Bj: result = C(i-1,j-1)+1 else: result = max(C(i,j-1),C(i-1,j) cacheget_key(i,j) = result return resultdef get_key(i,j): return str(i)+,+str(j)if _name_ = _main_: print C(len(A)-1,len(B)-1)上面程序的输出结果为5，我们也可以像背包问题一样，把上面代码改造成自底向上的求解方式，这里就省略了。但是实际应用中，我们可能更需要求最大公共子序列的序列，而不只是序列的长度，所以我们下面额外考虑一下如何输出这个结果。其实输出LCS字符串也是使用动态规划的方法，我们假设LCSi,j表示长度为i的字符串和长度为j的字符串的最大公共子序列，那么我们有以下状态转移函数：其中Ci,j是我们之前求得的最大子序列长度的缓存，根据上面的状态转移函数写出递归代码并不麻烦：#!/usr/bin/python# coding:utf-8Dynamic ProgrammingCACHE = # 为了下面表示方便，数组从1开始编号# 即当i,j为0的时候，公共子序列为0，属于极端情况A = 0, A, B, C, B, D, A, B, E, FB = 0, B, D, C, A, B, A, Fdef lcs_length(i, j): Calculate max sequence leng