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

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

❗❗❗必看:
下列题我全部都使用 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;}}
}