用java实现某公司预计明年有A, B, C, D四个新建项目,每个项目的投资额Ik及其投资后的收益Ek如下表所示,假设投资总额为3000万元,请问如何选择项目可以使总收益最大?
时间: 2024-05-10 11:20:58 浏览: 148
这是一个经典的0-1背包问题,可以使用动态规划算法进行解决。具体步骤如下:
1. 定义状态:设f[i][j]表示前i个项目,在总投资不超过j万元的情况下,可以获得的最大收益。
2. 初始化:f[0][j] = 0(前0个项目,无论投资多少,收益都为0);f[i][0] = 0(总投资为0,无论投资哪个项目,收益都为0)。
3. 状态转移方程:对于每个项目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}。
4. 最终结果:f[4][3000]即为总投资为3000万元时,可以获得的最大收益。
Java代码实现如下:
```
public class ProjectSelection {
public static void main(String[] args) {
int[] I = {400, 500, 200, 300}; // 投资额
int[] E = {500, 600, 300, 400}; // 投资后收益
int[][] f = new int[5][3001]; // 状态数组,f[i][j]表示前i个项目,在总投资不超过j万元的情况下,可以获得的最大收益
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 3000; j++) {
if (j < I[i-1]) {
f[i][j] = f[i-1][j]; // 不选第i个项目
} else {
f[i][j] = Math.max(f[i-1][j], f[i-1][j-I[i-1]] + E[i-1]); // 选第i个项目
}
}
}
System.out.println("总投资为3000万元时,可以获得的最大收益为:" + f[4][3000]);
}
}
```
阅读全文