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

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