某公司预计明年有A, B, C, D四个新建项目,每个项目的投资额Ik及其投资后的收益Ek如下表所示,假设投资总额为3000万元,请问如何选择项目可以使总收益最大?用Java实现
时间: 2024-05-06 13:20:43 浏览: 73
这是一个经典的背包问题,可以使用动态规划来解决。具体步骤如下:
1. 定义状态:设f(i, j)表示前i个项目中,投资额不超过j的情况下能够获得的最大收益。
2. 状态转移方程:对于第i个项目,可以选择投资或者不投资,因此有以下两种情况:
a. 不投资第i个项目:f(i, j) = f(i-1, j)
b. 投资第i个项目:f(i, j) = f(i-1, j-Ik) + Ek
综合两种情况,有:f(i, j) = max(f(i-1, j), f(i-1, j-Ik) + Ek)
3. 边界条件:当i=0或j=0时,f(i, j) = 0。
4. 最终结果:f(4, 3000)即为总收益最大的情况。
Java代码如下:
```
public class Investment {
public static void main(String[] args) {
int[] I = {500, 700, 800, 1000}; // 投资额
int[] E = {300, 400, 450, 500}; // 投资后的收益
int n = I.length; // 项目数
int m = 3000; // 总投资额
int[][] f = new int[n+1][m+1]; // 状态数组
// 动态规划求解
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j < I[i-1]) { // 投资额不足,不能选该项目
f[i][j] = f[i-1][j];
} else { // 能够选该项目,比较选择和不选择的收益
f[i][j] = Math.max(f[i-1][j], f[i-1][j-I[i-1]] + E[i-1]);
}
}
}
// 输出最大收益
System.out.println("总收益最大为:" + f[n][m]);
}
}
```
阅读全文