用Java实现金银岛贪心算法
时间: 2023-11-05 11:00:12 浏览: 53
金银岛问题是一个经典的贪心算法问题。以下是使用Java实现这个问题的代码:
```java
import java.util.Scanner;
public class JinYinDao {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 宝藏数量
int m = sc.nextInt(); // 背包容量
int[] v = new int[n]; // 每个宝藏的价值
int[] w = new int[n]; // 每个宝藏的重量
double[] p = new double[n]; // 每个宝藏的性价比
for (int i = 0; i < n; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
p[i] = (double) v[i] / w[i]; // 计算性价比
}
// 按照性价比从大到小排序
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i] < p[j]) {
double temp = p[i];
p[i] = p[j];
p[j] = temp;
int temp1 = v[i];
v[i] = v[j];
v[j] = temp1;
int temp2 = w[i];
w[i] = w[j];
w[j] = temp2;
}
}
}
double sum = 0; // 总价值
int i = 0; // 当前所选宝藏的下标
while (m > 0 && i < n) { // 背包还有空间且还有未选的宝藏
if (w[i] <= m) { // 当前宝藏可以全部装进背包
sum += v[i];
m -= w[i];
i++;
} else { // 当前宝藏装不下,只能装一部分
sum += p[i] * m;
break;
}
}
System.out.printf("%.2f", sum); // 输出总价值
}
}
```
这个程序首先读入宝藏的数量、背包的容量以及每个宝藏的价值和重量。然后,程序计算每个宝藏的性价比,并按照性价比从大到小排序。接着,程序使用贪心算法依次选取性价比最高的宝藏,直到背包无法再装下一个宝藏为止。最后,程序输出选中的宝藏的总价值。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)