动态规划例子

1、有 8 万元的投资可以投给 3 个过目，每个项目在不同筒子数额下（以万元为单位）的利润如下表投资额盈利012345678项目项目 105154080909598100项目 20515406070737475项目 30426404550515253请安排投资计划，使总的利润最大。写出你所设的状态变量、决策变量、状态转移方程与递推关系式和手工求解的详细步骤及结构。求解：状态变量：xk 表示留给项目k.n 的投资额，其中 n 为项目总个数，k=1.n.决策变量： uk 表示投给项目 k 的投资额 .允许决策集合：状态转移方程：递推关系式：其中，表示项目 k 的投资额为 uk 时的盈利 .针对本题， n = 3 ， xk 最大取 8手工详解过程：1. 初始化 k = 3x 3012345678f3(x 3)04264045505152532. k = 2精品文库欢迎下载2精品文库x 2012345678f2(x 2)0526406070861001103.k = 1x 1012345678f1(x 1)0526408090106120140欢迎下载3精品文库最终结果： 给项目 1 投资 4 万

2、元，项目 2 投资 4 万元，项目 3 不投资，将获得最大利润 140 万元 .python实现自顶向下，自底向上常用的算法设计思想主要有动态规划、贪婪法、随机化算法、回溯法等等，这些思想有重叠的部分，当面对一个问题的时候，从这几个思路入手往往都能得到一个还不错的答案。本来想把动态规划单独拿出来写三篇文章呢， 后来发现自己学疏才浅， 实在是只能讲一些皮毛，更深入的东西尝试构思了几次，也没有什么进展，打算每种设计思想就写一篇吧。动态规划（ Dynamic Programming ）是一种非常有用的用来解决复杂问题的算法，它通过把复杂问题分解为简单的子问题的方式来获得最优解。一、自顶向下和自底向上总体上来说，我们可以把动态规划的解法分为自顶向下和自底向上两种方式。一个问题如果可以使用动态规划来解决，那么它必须具有“最优子结构 ”，简单来说就是，如果该问题可以被分解为多个子问题，并且这些子问题有最优解，那这个问题才可以使用动态规划。自顶向下（ Top-Down）自顶向下的方式其实就是使用递归来求解子问题，最终解只需要调用递归式，子问题逐步往下层递归的求解。 我们可以使用缓存把每次求解出来的子

3、问题缓存起来， 下次调用的时候就不必再递归计算了。举例著名的斐波那契数列的计算：#!/usr/bin/env python# coding:utf-8def fib(number):if number = 0 or number = 1:return 1else:return fib(number - 1) + fib(number - 2)欢迎下载4精品文库if _name_ = _main_:print fib(35)有一点开发经验的人就能看出，fib(number-1)和 fib(number-2)会导致我们产生大量的重复计算，以上程序执行了14s 才出结果，现在，我们把每次计算出来的结果保存下来，下一次需要计算的时候直接取缓存，看看结果：#!/usr/bin/env python# coding:utf-8 cache = def fib(number):if number in cache:return cachenumberif number = 0 or number = 1:return 1else:cachenumber = fib(number - 1) + fib

4、(number - 2)return cachenumberif _name_ = _main_:print fib(35)耗费时间为0m0.053s效果提升非常明显。自底向上（ Bottom-Up）自底向上是另一种求解动态规划问题的方法， 它不使用递归式， 而是直接使用循环来计算所有可能的结果，往上层逐渐累加子问题的解。我们在求解子问题的最优解的同时， 也相当于是在求解整个问题的最优解。 其中最难的部分是找到求解最终问题的递归关系式，或者说状态转移方程。这里举一个01 背包问题的例子：你现在想买一大堆算法书，需要很多钱，所以你打算去抢一个商店，这个商店一共有n 个商品。问题在于，你只能最多拿W kg的东西。 wi 和 vi 分别表示第i 个商品的重量和价值。我们的目标就是在能拿的下的情况下，获得最大价值， 求解哪些物品可以放进背包。对于每一个商品你有两个选择：拿或者不拿。欢迎下载5精品文库首先我们要做的就是要找到“子问题 ”是什么，我们发现，每次背包新装进一个物品，就可以把剩余的承重能力作为一个新的背包来求解，一直递推到承重为0 的背包问题：作为一个聪明的贼，你用mi,w 表示偷到商

5、品的总价值，其中i 表示一共多少个商品，w 表示总重量，所以求解mi,w 就是我们的子问题，那么你看到某一个商品i 的时候，如何决定是不是要装进背包，有以下几点考虑：1. 该物品的重量大于背包的总重量，不考虑，换下一个商品；2. 该商品的重量小于背包的总重量，那么我们尝试把它装进去，如果装不下就把其他东西换出来，看看装进去后的总价值是不是更高了，否则还是按照之前的装法；3.极端情况，所有的物品都装不下或者背包的承重能力为0，那么总价值都是0；由以上的分析，我们可以得出mi,w 的状态转移方程为：有了状态转移方程，那么写起代码来就非常简单了，首先看一下自顶向下的递归方式，比较容易理解：#!/usr/bin/env python# coding:utf-8 cache = 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)r

6、esult = 0# 特殊情况if i = 0 or w = 0:欢迎下载6精品文库return 0# w wiif w =wiif 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 ,ielse:print did not take,icachestr(i)+,+str(w) = resultreturn resultif _name_ = _main_:# 背包把所有东西都能装进去做假设开始print m(len(items)-1,W)改造成非递归，即循环的方式，从底向上求解：#!/usr/bin/env python# coding:utf-8 cache = 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) = 0for i in items:欢迎下载7精品文库cacheget_key(i,0) = 0for 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)

《动态规划例子》由会员M****1分享，可在线阅读，更多相关《动态规划例子》请在金锄头文库上搜索。