动态规划假定有一笔资金b=100万元,现在有7个项目,可以投资。各项目的投资额和收益如下: 项目 1 2 3 4 5 6 7 投资额万 10 14 19 21 28 32 40 收益万 3 4 5 6 7 9 13 问怎样投资收益最大?
时间: 2024-05-04 17:15:17 浏览: 7
这是一个经典的动态规划问题,可以采用以下步骤求解:
1. 定义状态:设f[i][j]表示前i个项目中,投资额不超过j万元时的最大收益。
2. 初始化状态:f[0][j] = 0(前0个项目投资额为0时,收益为0),f[i][0] = 0(不投资时,收益为0)。
3. 状态转移方程:对于第i个项目,有两种情况:投资或不投资。如果投资,收益为f[i-1][j-投资额]+收益额;如果不投资,收益为f[i-1][j]。因此有:
f[i][j] = max{f[i-1][j], f[i-1][j-投资额]+收益额} (1<=i<=7,1<=j<=100)
4. 最终结果:f[7][100]即为投资额不超过100万元时的最大收益。
根据以上步骤,可以使用动态规划算法求解该问题。具体代码如下:
```
int b = 100;
int invest[7] = {10,14,19,21,28,32,40};
int profit[7] = {3,4,5,6,7,9,13};
int f[8][101] = {0};
for(int i=1; i<=7; i++){
for(int j=1; j<=b; j++){
if(j >= invest[i-1]){
f[i][j] = max(f[i-1][j], f[i-1][j-invest[i-1]]+profit[i-1]);
}else{
f[i][j] = f[i-1][j];
}
}
}
cout << "投资额不超过100万元时的最大收益为:" << f[7][100] << "万元" << endl;
```
运行结果为:投资额不超过100万元时的最大收益为:24万元。
因此,最优投资方案为投资项目1、2、3、4、6,总投资额为96万元,总收益为24万元。