资源描述：
《动态规划例子》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、有8万元的投资可以投给3个过目，每个项目在不同筒子数额下（以万元为单位）的利润如下表投资额盈利项目012345678项目105154080909598100项目20515406070737475项目30426404550515253请安排投资计划，使总的利润最大。写出你所设的状态变量、决策变量、状态转移方程与递推关系式和手工求解的详细步骤及结构。求解：状态变量：xk表示留给项目k..n的投资额，其中n为项目总个数，k=1..n.决策变量：uk表示投给项目k的投资额.允许决策集合：Dkxk=uk
2、0≤uk≤xk状态转移方程：xk+1=xk-uk递推关系式：f
3、kxk=uk∈Dkxkmaxgkuk+fk+1xk-ukk=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,g2
4、2+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
5、+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
6、,g28+f30=max0+53,5+52,15+51,40+50,60+45,70+40,73+26,74+4,75+0=110.x2012345678f2(x2)0526406070861001101.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最
7、终结果：给项目1投资4万元，项目2投资4万元，项目3不投资，将获得最大利润140万元. python实现自顶向下，自底向上常用的算法设计思想主要有动态规划、贪婪法、随机化算法、回溯法等等，这些思想有重叠的部分，当面对一个问题的时候，从这几个思路入手往往都能得到一个还不错的答案。本来想把动态规划单独拿出来写三篇文章呢，后来发现自己学疏才浅，实在是只能讲一些皮毛，更深入的东西尝试构思了几次，也没有什么进展，打算每种设计思想就写一篇吧。动态规划（DynamicProgramming）是一种非常有用的用来解决复杂问题的算法，它通过把复杂问题分解为简单的子问题的方式
8、来获得最优解。一、自顶向下和自底向上总体上来说，我们可以把动态规划的解法分为自顶向下和自底向上两种方式。一个问题如果可以使用动态规划来解决，那么它必须具有“最优子结构”，简单来说就是，如果该问题可以被分解为多个子问题，并且这些子问题有最优解，那这个问题才可以使用动态规划。自顶向下（Top-Down）自顶向下的方式其实就是使用递归来求解子问题，最终解只需要调用递归式，子问题逐步往下层递归的求解。我们可以使用缓存把每次求解出来的子问题缓存起来，下次调用的时候就不必再递归计算了。举例著名的斐波那契数列的计算：#!/usr/bin/envpython#coding
9、:utf-8deffib(number):ifnumber==0o
