动态规划例子.doc

《动态规划例子.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.有8万元的投资可以投给3个过目，每个项目在不同筒子数额下（以万元为单位）的利润如下表投资额盈利项目012345678项目105154080909598100项目20515406070737475项目30426404550515253请安排投资计划，使总的利润最大。写出你所设的状态变量、决策变量、状态转移方程与递推关系式和手工求解的详细步骤及结构。求解：状态变量：xk表示留给项目k..n的投资额，其中n为项目总个数，k=1..n.决策变量：uk表示投给项目k的投资额.允许决策集合：状态转移方程：递推关系式：其中，表示项目k的投资额为uk时的盈利.针对本题，n=3，xk最大取8W

2、ord资料.手工详解过程：1.初始化k=3x3012345678f3(x3)04264045505152532.k=2Word资料.x2012345678f2(x2)0526406070861001101.k=1x1012345678f1(x1)0526408090106120140最终结果：给项目1投资4万元，项目2投资4万元，项目3不投资，将获得最大利润140万元. python实现自顶向下，自底向上常用的算法设计思想主要有动态规划、贪婪法、随机化算法、回溯法等等，这些思想有重叠的部分，当面对一个问题的时候，从这几个思路入手往往都能得到一个还不错的答案。本来想把动态规划单独

3、拿出来写三篇文章呢，后来发现自己学疏才浅，实在是只能讲一些皮毛，更深入的东西尝试构思了几次，也没有什么进展，打算每种设计思想就写一篇吧。Word资料.动态规划（DynamicProgramming）是一种非常有用的用来解决复杂问题的算法，它通过把复杂问题分解为简单的子问题的方式来获得最优解。一、自顶向下和自底向上总体上来说，我们可以把动态规划的解法分为自顶向下和自底向上两种方式。一个问题如果可以使用动态规划来解决，那么它必须具有“最优子结构”，简单来说就是，如果该问题可以被分解为多个子问题，并且这些子问题有最优解，那这个问题才可以使用动态规划。自顶向下（Top-Down）自顶向

4、下的方式其实就是使用递归来求解子问题，最终解只需要调用递归式，子问题逐步往下层递归的求解。我们可以使用缓存把每次求解出来的子问题缓存起来，下次调用的时候就不必再递归计算了。举例著名的斐波那契数列的计算：#!/usr/bin/envpython#coding:utf-8deffib(number):ifnumber==0ornumber==1:return1else:returnfib(number-1)+fib(number-2)Word资料.if__name__=='__main__':printfib(35)有一点开发经验的人就能看出，fib(number-1)和fib(n

5、umber-2)会导致我们产生大量的重复计算，以上程序执行了14s才出结果，现在，我们把每次计算出来的结果保存下来，下一次需要计算的时候直接取缓存，看看结果：#!/usr/bin/envpython#coding:utf-8cache={}deffib(number):ifnumberincache:returncache[number]ifnumber==0ornumber==1:return1else:cache[number]=fib(number-1)+fib(number-2)returncache[number]if__name__=='__main__':prin

6、tfib(35)耗费时间为0m0.053s效果提升非常明显。Word资料.自底向上（Bottom-Up）自底向上是另一种求解动态规划问题的方法，它不使用递归式，而是直接使用循环来计算所有可能的结果，往上层逐渐累加子问题的解。我们在求解子问题的最优解的同时，也相当于是在求解整个问题的最优解。其中最难的部分是找到求解最终问题的递归关系式，或者说状态转移方程。这里举一个01背包问题的例子：你现在想买一大堆算法书，需要很多钱，所以你打算去抢一个商店，这个商店一共有n个商品。问题在于，你只能最多拿Wkg的东西。wi和vi分别表示第i个商品的重量和价值。我们的目标就是在能拿的下的情况下，获

7、得最大价值，求解哪些物品可以放进背包。对于每一个商品你有两个选择：拿或者不拿。首先我们要做的就是要找到“子问题”是什么，我们发现，每次背包新装进一个物品，就可以把剩余的承重能力作为一个新的背包来求解，一直递推到承重为0的背包问题：作为一个聪明的贼，你用 m[i,w]表示偷到商品的总价值，其中i表示一共多少个商品，w表示总重量，所以求解m[i,w]就是我们的子问题，那么你看到某一个商品i的时候，如何决定是不是要装进背包，有以下几点考虑：1.该物品的重量大于背包的总重量，不考虑，换下一个商品；2