【代码+详解】算法题 : 金银岛

本文主要是介绍【代码+详解】算法题 : 金银岛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

❗❗❗必看:
下列题我全部都使用 Java 语言写的,并且均可以提交成功,获得Accepted 结果的. 如果代码和详解看了之后,对答案有任何疑问,都可以在评论区提出来,我都会一个一个回答.

❗❗❗感谢大家的支持,如果喜欢我的博客,关注 点赞 收藏 评论一波,非常感谢!!!

题目:金银岛

某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类, 每种金属重量不同，分别为n(1), n(2), … , n(s)，同时每个种类的金属总的价值也不同，分别为v(1),v(2), …, v(s)。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。

Input

第1行是测试数据的组数k，后面跟着k组输入。

每组测试数据占3行，第1行是一个正整数w (1 <= w <= 10000)，表示口袋承重上限。第2行是一个正整数s (1 <= s <=100)，表示金属种类。第3行有2s个正整数，分别为n(1), v(1), n(2), v(2), … , n(s), v(s)分别为第一种，第二种，…，第s种金属的总重量和总价值(1 <= n(i) <= 10000, 1 <= v(i) <= 10000)。

Output

k行，每行输出对应一个输入。输出应精确到小数点后2位。

样例测试

输入

2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

输出

171.93
508.00

代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int k = sc.nextInt(); // 读取测试数据的组数List<int[]> testCases = new ArrayList<>();for (int i = 0; i < k; i++) {int w = sc.nextInt(); // 读取口袋承重上限int s = sc.nextInt(); // 读取金属种类int[] metals = new int[2 * s + 2];metals[0] = w;metals[1] = s;for (int j = 2; j < 2 * s + 2; j++) {metals[j] = sc.nextInt(); // 读取每种金属的重量和价值}testCases.add(metals);}List<String> results = maxMetalValue(k, testCases);for (String result : results) {System.out.println(result); // 输出结果}sc.close();}public static List<String> maxMetalValue(int k, List<int[]> testCases) {List<String> results = new ArrayList<>();for (int i = 0; i < k; i++) {int w = testCases.get(i)[0];int s = testCases.get(i)[1];int[] metals = Arrays.copyOfRange(testCases.get(i), 2, testCases.get(i).length);List<Metal> metalList = new ArrayList<>();for (int j = 0; j < s; j++) {int weight = metals[2 * j];int value = metals[2 * j + 1];metalList.add(new Metal(weight, value));}metalList.sort((m1, m2) -> Double.compare(m2.unitValue, m1.unitValue));double totalValue = 0.0;for (Metal metal : metalList) {if (w <= 0) break;if (metal.weight <= w) {totalValue += metal.value;w -= metal.weight;} else {totalValue += metal.unitValue * w;w = 0;}}results.add(String.format("%.2f", totalValue)); // 这里进行格式化并添加到结果中}return results;}static class Metal {double unitValue;int weight;int value;public Metal(int weight, int value) {this.weight = weight;this.value = value;this.unitValue = (double) value / weight;}}
}

图示

画的有点抽象,但是非常建议把下面的图示结合代码一起看,学起来的效率非常高.保证一看就会

金银岛算法题解

初步思路

这个问题是典型的“贪心算法”应用。通过计算每种金属的单位价值（即每单位重量的价值），然后优先选择单位价值最高的金属直到达到口袋承重上限，可以最大化KID能带走的金属总价值。

具体步骤

1. 读取输入数据：从输入中读取测试数据的组数k，之后对每组测试数据分别处理。
2. 数据解析：对每组测试数据，先读取口袋承重上限w，然后读取金属种类数s，接着读取每种金属的重量和价值。
3. 计算单位价值：为每种金属计算单位价值（即每单位重量的价值 = 总价值 / 总重量）。
4. 按单位价值排序：将金属按单位价值从高到低排序。
5. 贪心选择：从单位价值最高的金属开始，尽量多地选择直到达到承重上限。如果当前金属重量超过剩余承重上限，则选择部分金属使其正好达到承重上限。
6. 记录结果：记录每组测试数据的最大金属总价值，并格式化到小数点后两位。

总结方法

这种方法的关键在于贪心选择的策略，通过单位价值的排序和逐步选择，确保每一步都尽可能提高总价值。这样的策略在面对能够部分选择的物品问题时非常有效。通过这一题，我们可以更好地理解贪心算法在解决部分选择问题中的应用，并学习如何通过排序和逐步选择来达到最优解。

这篇关于【代码+详解】算法题 : 金银岛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---