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

❗❗❗必看:
下列题我全部都使用 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. 记录结果：记录每组测试数据的最大金属总价值，并格式化到小数点后两位。

总结方法

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