用java实现金银岛贪心算法
时间: 2023-10-01 10:10:27 浏览: 66
金银岛问题是一个著名的贪心算法问题,可以用Java语言实现。下面是一个简单的实现:
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // n个金矿
int w = sc.nextInt(); // 背包容量
int[] g = new int[n]; // 每个金矿的黄金量
int[] p = new int[n]; // 每个金矿需要的人数
for (int i = 0; i < n; i++) {
g[i] = sc.nextInt();
p[i] = sc.nextInt();
}
int[][] dp = new int[n + 1][w + 1]; // 动态规划数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (j < p[i - 1]) { // 当前背包容量不能装下第i个金矿
dp[i][j] = dp[i - 1][j];
} else { // 可以装下第i个金矿
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - p[i - 1]] + g[i - 1]);
}
}
}
System.out.println(dp[n][w]); // 输出最大黄金量
}
}
```
输入格式如下:
```
5 10
400 5
500 5
200 3
300 4
350 3
```
其中第一行输入金矿数和背包容量,接下来每行输入每个金矿的黄金量和需要的人数。
输出结果为最大黄金量,即:
```
900
```