算法分析与设计之动态规划法
_——_投资问题
问题描述：投资问题就是考虑如何把有限资源分配给若干个工程的问题。
给定条件：
1.资源总数（设为a）
2.工程个数（设为n）
3.每项工程投资的利润（不同数目的投资所获得的利润不同），用向量Gi (1≦i≦n)表示。
n
问题求解：
求出一个a的分划x1 , x2 ,….., xn ,0≦xi≦a, 且∑xi≦a,使得以下式表示的利润为最大：
i=1 n G(a)= ∑Gi (xj ) 0≦xj≦a i=1
其中Gi (xj )是把资源xj分配给第I项工程能获得的最大利润。
问题分析：
i）若Gi是x的线性函数，则为线性规划问题。
ii）若Gi不是线性函数，则要用动态规划求最佳分配。
用总量为a的资金在n个项目上进行投资以取得最大的利润，可以转化为下述的问题：
将总量资金a分为两部分z(0≦z≦a)及a-z，分别用在第n个项目及剩下的n-1个项目上进行投资，获得的最大利润G(a)=max(第n个项目上资金量为z的利润与用a-z的资金在n-1个项目上投资的最大利润之和)。这样问题就转化为”求用a-z的资金在n-1个项目上投资的最大利润”，与我们的原问题” 求总量为a的资金在n个项目上进行投资以取得最大的利润”性质完全一致，仅仅是问题的规模比原问题少了一个项目，如此将问题的规模细化下去，一直到项目数为1为止，则问题迎刃而解。我们在对原问题进行”分而治之”的过程当中，最终实现了最优化的求解。
问题解决方案：
设fi (x)：前i个项目共投资资金x所产生的最大利润；di (x)：产生fi (x)在项目i上的资金数。
由上分析可给出投资问题的动态规划函数方程：
f1 (x)= G1 (x); d1 (x)=x x=0,1……a fi (x)=max[Gi (z)+ fi-1 (x-z)] z=0,1……x; x=0,1……a di (x)=产生fi (x)的z值 i=2,3…..n;
问题举例：
设有8（万元）的投资可分给3个项目，每个项目的利润函数如下表（一）所示：
表（一）利润函数表
x 0 1 2 3 4 5 6 7 8 G1 (x) G2 (x) G3 (x) 0 5 15 40 80 90 95 98 100 0 5 15 40 60 70 73 74 75 0 4 26 40 45 50 51 52 53 x 0 1 2 3 4 5 6 7 8 G1 (x) G2 (x) G3 (x) 0 5 15 40 80 90 95 98 100 0 5 15 40 60 70 73 74 75 0 4 26 40 45 50 51 52 53
解题步骤：
第1步：设项目1是可用于投资的唯一项目，把x万元投资到项目1，利润为
f1 (x)= G1 (x)
这就得到表（二）的最后一行的值，投资到项目1的最优数量为
d1 (x)=x x=0,1……8；
第二步：设资金8万元可投资到项目1和项目2。由第1步已知任意数量的资源投资到项目1所产生的最优，所以下到各种和式中的最大值就是目前情况下的最大利润：
G2 (0)+ f1 (8)=0+100=100 G2 (1)+ f1 (7)=5+98=103 G2 (2)+ f1 (6)=15+95=110 G2 (3)+ f1 (5)=40+90=130 G2 (4)+ f1 (4)=80+60=140 G2 (5)+ f1 (3)=70+40=110 G2 (6)+ f1 (2)=73+15=88 G2 (7)+ f1 (1)=74+5=79 G2 (8)+ f1 (0)=75+0=75
可见将8万元投资于项目1和2 ，所能获得的最大利润f2 (8)及投资到项目2的最优数量分别为：
f2 (8)=max[G2 (z)+ f1 (8-z)]=140 z=0,1……8 d2 (8)=4；
第三步：假设以任意x(≠8)万元投资到项目1和2，对每个x值，计算从项目1和2所产生的最优利润，即：
f2 (x)=max[G2 (z)+ f1 (x-z)] z=0,1……x;
投资到项目2的数量为
d2 (x)=产生f2 (x)的z值。
得到所表（二）的结果。
第四步：将8万元投资于3个项目，这就是原问题。则f3 (8)应取下述各量的最大值：
G3 (0)+ f2 (8)=0+140=140 G3 (1)+ f2 (7)=4+120=124 G3 (2)+ f2 (6)=26+96=126 G3 (3)+ f2 (5)=40+90=130 G3 (4)+ f2 (4)=45+80=125 G3 (5)+ f2 (3)=50+40=90 G3 (6)+ f2 (2)=51+15=66 G3 (7)+ f2 (1)=52+5=57 G3 (8)+ f2 (0)=53+0=53
因此将8万元以最优方式投资到3个项目时所获得的最大利润及投资到项目3的分别为：
f3 (8) =G3 (0)+ f2 (8)=140 d3 (8)=0；
表（二）向项目1，2投资所到的利润表
x 0 1 2 3 4 5 6 7 8 f1 (x) d1 (x) f2 (x) d2 (x) 0 5 15 40 80 90 95 98 100 0 1 2 3 4 5 6 7 8 0 5 15 40 80 90 95 120 140 0 1 2 3 0 0 0 3 4 x 0 1 2 3 4 5 6 7 8 f1 (x) d1 (x) f2 (x) d2 (x) 0 5 15 40 80 90 95 98 100 0 1 2 3 4 5 6 7 8 0 5 15 40 80 90 95 120 140 0 1 2 3 0 0 0 3 4
因为d3 (8)=0；故剩下8万元要最优的投资到项目1和2中。由表（二）易知，当项目1和2 可用时，d2 (8)=4表示投资到项目2的最优数量，因此项目1应投资剩下的4万元。