文档介绍：. .
优选
有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的投资额.
允许决策集合：
状态转移方程：
递推关系式：
其中，表示工程k的投资额为uk时的盈利.
针对此题，n = 3，xk最大取8
手工详解过程：
初始化k = 3
x3
0
1
2
3
4
5
6
7
8
f3(x3)
0
4
26
40
45
50
51
52
53
. .
优选
k = 2
x2
0
1
2
3
4
5
6
7
8
f2(x2)
0
5
26
40
60
70
86
100
110
k = 1
x1
0
1
2
3
4
5
6
7
8
f1(x1)
0
5
26
40
80
90
106
120
140
最终结果：给工程1投资4万元，工程2投资4万元，工程3不投资，将获得最大利润140万元.
python实现自顶向下，自底向上
常用的算法设计思想主要有动态规划、贪婪法、随机化算法、回溯法等等，这些思想有重叠的局部，当面对一个问题的时候，从这几个思路入手往往都能得到一个还不错的答案。
本来想把动态规划单独拿出来写三篇文章呢，后来发现自己学疏才浅，实在是只能讲一些皮毛，更深入的东西尝试构思了几次，也没有什么进展，打算每种设计思想就写一篇吧。
动态规划〔Dynamic Programming〕是一种非常有用的用来解决复杂问题的算法，它通过把复杂问题分解为简单的子问题的方式来获得最优解。
一、自顶向下和自底向上
总体上来说，我们可以把动态规划的解法分为自顶向下和自底向上两种方式。
. .
优选
一个问题如果可以使用动态规划来解决，那么它必须具有"最优子构造〞，简单来说就是，如果该问题可以被分解为多个子问题，并且这些子问题有最优解，那这个问题才可以使用动态规划。
自顶向下〔Top-Down〕
自顶向下的方式其实就是使用递归来求解子问题，最终解只需要调用递归式，子问题逐步往下层递归的求解。我们可以使用缓存把每次求解出来的子问题缓存起来，下次调用的时候就不必再递归计算了。
举例著名的斐波那契数列的计算：
*!/usr/bin/env python
* coding:utf-8
deffib(number):
ifnumber==0ornumber==1:
return1
else:
returnfib(number-1)+fib(number-2)
if__name__=='__main__':
printfib(35)
有一点开发经历的人就能看出，fib(number-1)和fib(number-2)会导致我们产生大量的重复计算，以上程序执行了14s才出结果，现在，我们把每次计算出来的结果保存下来，下一次需要计算的时候直接取缓存，看看结果：
. .
优选
*!/usr/bin/env python
* coding:utf-8
cache={}
deffib(number):
ifnumberincache:
returncache[number]
ifnumber==0ornumber==1:
return1
else:
cache[number]=fib(number-1)+fib(number-2)
returncache[number]
if__name__=='__main__':
printfib(35)
消耗时间为效果提升非常明显。
自底向上〔Bottom-Up〕
自底向上是另一种求解动态规划问题的方法，它不使用递归式，而是直接使用循环来计算所有可能的结果，往上层逐渐累加子问题的解。
我们在求解子问题的最优解的同时，也相当于是在求解整个