动态规划算法典型应用的投资问题内容：设m元钱、n项投资，函数fI(x ) f_I ) x ) fi ) x )表示将x元投入I项项目所带来的收益，I=1，2，……，n，n
动态规划算法需要将问题分割为子问题，从规模小的问题开始计算，在计算出某个问题时将该问题的计算过程用于之前以及计算出的子问题的结果来提高效率。 这个问题的我们可以根据两个参数来划分子问题的规模。 在每种情况下，在分配前k个项目以及x万元之前，可以使用优化函数fk(x ) f_k ) x ) x )来表示前k个项目投入x万元的最大收益。
因此规模最小的问题是f1(x ) f_1) x ) f1 ) x )即x万元只分配给第一个项目。 显然，此时获得的最大益处是利益函数fI(x )fI(x )fI(x )。 也就是说按照f1(1)=f1 )1) f_1)=f_1(1)1) F1 )1)=f1 )1)2)=f_2) $的顺序类推
之后，如果规模再大一点，就会把x万元分配给前两个项目。 例如，f2(1) f2(1)意味着将1万元前分配给前两个项目。 那也有两种可能性。 第二个项目0万元，第一个项目1万元，第二个项目1万元，第一个项目0万元。 以最初的可能性为例。 第二个项目分配0万元，根据利润函数f 2
( 0 ) f_2(0) f2(0)来直接得到，当然分配0元当然收益0啦2333，然后前1个项目分配1万元获得的收益多少呢？这时候就可以直接用前一个规模的子问题也就是 F 1 ( 1 ) F_1(1) F1(1)来计算啦！最后只要比较一下两种可能性谁大谁小，选择大的就得到了这个规模问题的答案。我们总结一下后就可以得到递推方程。
F k ( x ) = m a x 0 ⩽ x k ⩽ x { f k ( x k ) + F k − 1 ( x − x k ) } F_k(x) = underset {0leqslant x_k leqslant x} {max} {f_k(x_k) + F_{k-1}(x-x_k)} Fk(x)=0⩽xk⩽xmax{fk(xk)+Fk−1(x−xk)}
最后我根据书本的数据，写了一个程序，正确得出了把5万元分配给4个项目的最大收益，可以说小有成就233
//投资问题，m元钱，n项投资，f[i][x]表示将x元投入第i项项目所产生的收益，问如何分配这m元钱使得投资的收益最高？//输入：m n f[n][m]（根据课本的数据手动给定）//输出：最高收益以及如何分配的方法#include <iostream>#include <algorithm>using namespace std;int main(){ int m = 5; int n = 4; int f[5][6] = {0}; f[1][1] = 11, f[1][2] = 12, f[1][3] = 13, f[1][4] = 14, f[1][5] = 15; f[2][1] = 0, f[2][2] = 5, f[2][3] = 10, f[2][4] = 15, f[2][5] = 20; f[3][1] = 2, f[3][2] = 10, f[3][3] = 30, f[3][4] = 32, f[3][5] = 40; f[4][1] = 20, f[4][2] = 21, f[4][3] = 22, f[4][4] = 23, f[4][5] = 24; int F[5][6] = {0}; //F[k][x] 表示 将x万元钱分配到前k个项目取得的最大收益 int x[5][6] = {0}; //用来储存当F[k][x]取得最大值时, 第k个项目被投资了多少万元钱 for (int i = 1; i <= 5; i++) { F[1][i] = f[1][i]; //当把i万元前全部分配给第一个项目的时候，取得最大的收益就是对应的收益函数f x[1][i] = i; //因为只有一个项目，全部投！ } for (int i = 2; i <= 4; i++) //枚举分配前两个项目、前三个，前四个 { for (int j = 1; j <= 5; j++) //枚举投资1万元，2万云…… { int _max = 0; for (int k = 0; k <= j; k++) { if (f[i][k] + F[i - 1][j - k] > _max) { _max = f[i][k] + F[i - 1][j - k]; //更新当前情况的最大收益 x[i][j] = k; //记录下当用j万元钱给前i个项目投资时，第i个项目被投资的钱数k } } F[i][j] = _max; } } cout << "最大收益额为" << F[4][5] << endl; int money = 5; for (int i = 4; i >= 1; i--) //解的追溯 { cout << "第" << i << "个项目投资" << x[i][money] << "元" << endl; money -= x[i][money]; } return 0;}运行结果
好好学习，天天向上！