动态规划算法之投资问题
投资问题的描述:  fi(x)表⽰的是把 x 元钱投资到第 i 个项⽬所获得收益。课堂上⽼师说,约束条件必须满⾜投资的钱数等于总共的钱数
举例说明,更容易理解:在这个表格中,⽐如坐标(1,0)对应的值为11,这个含义就是说把 1 万元投资到项⽬1中,获得的收益是  11万元。坐标(3,4)的值为 22,这个含义就是说把 3 万元投资到项⽬ 4 中,获得的收益是  22万元。
⼦问题的界定:
k代表的含义是,考虑到第⼏个项⽬
x代表的含义是:你投资的钱数不超过 x
所以,这⾥的 k 和 x 是两个性质不同的参数。
我们之前学的矩阵链相乘,问题中的 i ,j 是矩阵的下标。是同样类型的参数。
再讨论计算顺序,先定下所要投资的项⽬,是前 k 个,从1,k
当k 的值确定以后,再让 x 变化。⽐如,当k的值为5时,我们考虑 x 为1,2, 时,获得的收益。
小项目投资优化函数的递推⽅程: Fk(x)表⽰的意思是把 x 元投资给前  k 个项⽬获得的最⼤收益。
x的范围(投资的总的钱数)是0 到 x
k 的范围是 1 到 n (总共有  n 个项⽬)
那么 Fk(x) 的值应该是对第k个项⽬投资了 xk 元后的收益  +  把剩下的钱(x-xk)投给前  k-1个项⽬的总的收益  Fk-1(x-xk)
那么,这个 xk的值可以从 0 到  x,就是说,可以⼀分钱也不投资给第k个项⽬,也可以把所有钱都投资给这个项⽬,所以,这⾥要遍历
x+1次才可以获得收益的最⼤值。
下⾯举例说明,当 k=1 时,就是说考虑前⾯第⼀个项⽬。只投资第⼀个项⽬。
把 0元投资给第⼀个项⽬,收益为0元,
把 1 元投资给第⼀个项⽬,收益为 11元
把 2 元投资给第⼀个项⽬,收益为 12 元,以此类推
举例说明,当K=2 时,我们考虑把钱投资给前 2 个项⽬。
K确定以后,我们就要来遍历  x ,x是投资的总的钱数,范围是从 0 到 5.
当 x= 5时,我们分析情况:
⽅案有 :(0,5),(5,0),(1,4),(4,1),(2,3),(3,2)
F2( x=5)=max{  f1(0)+f2(5) , f1(5)+f2(0) , f1(1)+f2(4) , f1(4)+f2(1) , f1(2)+f2(3) , f1(3)+f2(2) }
max { 0 +20 , 15+0 , 11 +15 , 14 +0 ,12 + 10 , 13+5 } ,所以,此时最⼤的收益是 26 万元。
备忘录和解:
F1(x )就是我们刚刚提到的,把 x万元投在到前  k 个项⽬中,这⾥ k=1
那么, x 1(x)  是什么意思呢,这是标记函数,表⽰的意思是,你得到当前的最⼤收益时,你给了最后⼀个项⽬多少钱
⽐如,我们刚刚算的 F 2(5),我们把5万元投资到前  2 个项⽬中,当获得最⼤收益 26 万元时,我们给第⼆个项⽬
投资的是4万元。上⾯已经说的很清楚了。
那我们来举个不同的例⼦分析⼀下。
⽐如我要追踪我投资 4万元给这四个项⽬获得的最⼤收益,显然是 50万元。
此时,给第四个项⽬的投资是1 万元, x 4( 4)=1, 也就是说, x4=1,d第四个项⽬投资 1万元x3(3)= 3, 也就是说,我们把剩余的3 万元全部投资给了第三个项⽬
剩下的钱为 0 ,⽆法投资
时间复杂度分析:
有两种分析⽅法,
⼩结:
代码实现:
#include<iostream>
#include<vector>
using namespace std;
int main() {
int m, n;//m元钱,n项投资
int i, j;//循环辅助变量
int tmp_m,tmp_F=0;//tem_m代表给第i个项⽬投⼊的钱数  0<=tmp<=j;tmp_F代表⼀次循环中的钱数
cin >> m >> n;
vector<vector<int>> f(n, vector<int>(m + 1));//f[i][x], 0<i<=n,0<=x<=m;
vector<vector<int>> F(n, vector<int>(m + 1));//F[i][x],将x元钱投⼊到前i个项⽬上最⼤的收益
for (i = 0; i < n; ++i) {
f[i][0] = 0;//在第(i+1)个项⽬上投⼊0元,收益为0,注意i从0开始
}
for (i = 0; i < n; ++i) {
for (j = 1; j < m + 1; ++j) {//j从1开始,也就是从f[0][1]开始
cin >> f[i][j];
}
}
//给F[0][0-m]赋值
for (j = 0; j < m + 1; ++j) {
F[0][j] = f[0][j];//第⼀个项⽬上投⼊0-m元钱的最⼤收益等于f[0][0-m]
}
for (i = 1; i < n; ++i) {//项⽬循环,从1开始,也就是从前2个项⽬开始算,因为第⼀个项⽬已经赋值
for (j = 0; j < m + 1; ++j) {//钱数循环从0开始
for (tmp_m = 0; tmp_m <= j; ++tmp_m) {
tmp_F = F[i - 1][j - tmp_m] + f[i][tmp_m];
if (tmp_F > F[i][j])
F[i][j] = tmp_F;
}
}
}
cout << "the max profit is : " << F[n - 1][m] << endl;
}
View Code
实现结果:
控制台输⼊说明:
输⼊:第⼀⾏为总钱数m和总项⽬数n;接下来为n⾏输⼊,每⾏m个,代表f[i][x]。
输出:最⼤收益。