四个实例超详细讲解Java 贪心和枚举的特点与使用

一、贪心算法

1. 特点

贪心算法是一种近似算法，它通过每一步的局部最优选择来达到全局最优解。贪心算法具有以下特点：

• 贪心选择性质：采用当前最优的选择，在局部达到最优解。
• 子问题最优性质：当前问题可以分解成多个子问题，每个子问题可以独立的求解，每个子问题的最优解包含在全局最优解中。
• 贪心策略：贪心算法强调局部最优，具有贪心策略的问题不能用动态规划求解。

2. 使用场景

贪心算法主要适用于满足以下条件的问题：

• 可分解为子问题的形式
• 每个子问题都有一种最优解可以通过局部最优得到整个问题的最优解
• 每个子问题的最优解能够推导出全局最优解

3. 示例一：找零钱问题

假设有一定面值的纸币和硬币，在某次消费后，需要找零 102 元，请问如何使用贪心算法进行人民币找零问题？

找零钱问题可以采用贪心策略得出最优解。每一次应该选择当前面值最大的钱币，直到总面值达到找零金额。

考虑到纸币的面值为 100 元、50 元、20 元、10 元、5 元、1 元，可以采用以下贪心策略：

• 如果还需要找的钱数大于等于 100 元，就先找一个 100 元的钞票，然后问题就被转化为找 2 元钱；
• 如果还需要找的钱数小于 100 元但大于等于 50 元，就先找一个 50 元，然后问题就被转化为找 52 元钱；
• 以此类推…

如下是采用贪心算法求解该问题的 Java 代码实现：

public static void main(String[] args) {
    greedy(102);
}

private static void greedy(int money) {
    int[] faces = {100, 50, 20, 10, 5, 1};
    int count = 0;

    for (int i = 0; i < faces.length && money > 0; i++) {
        int num = money / faces[i];
        count += num;
        money -= num * faces[i];
        System.out.println("需要面额为" + faces[i] + "的张数：" + num);
    }

    System.out.println("总共找零：" + count + "张");
}

二、枚举算法

1. 特点

枚举算法，也被称为古代暴力算法，是一种朴素的搜索策略，它逐步枚举各种可能的结果，最终找到既满足条件又合法的结果。枚举算法具有以下特点：

• 枚举算法遍历所有可能的答案，虽然费时费力，但具有可以得到正确答案的优势。
• 枚举算法的时间复杂度极高，适用于数据量较小的问题。

2. 使用场景

枚举算法主要适用于以下条件的问题：

• 数据量较小且不可用更高效的算法解决。
• 问题本身即不需要特殊的数据结构，也不存在特殊的条件需要满足。

3. 示例二：鸡兔同笼问题

鸡兔同笼问题描述如下：又称“百钱百鸡”问题，有若干只鸡和兔子，在一起关进笼子中，共有头、只脚，求鸡和兔子的数量。

假设鸡的数量为 x，兔子的数量为 y，题目可以描述为：

x + y = heads
2x + 4y = legs

其中 heads 代表总的头数量，legs 代表总的脚数量，根据题意可知：

• 每只鸡有一个头，每只兔子有两个头，因此头的总共数量就是鸡和兔子总数量的两倍。
• 每只鸡有两只脚，每只兔子有四只脚，因此脚的总共数量就是鸡和兔子总数量的 2 倍，再加上鸡和兔子之间相加的两组腿数量。

根据以上两个条件，可以将鸡兔同笼问题转化为如下代码：

public static void main(String[] args) {
    int heads = 35;
    int legs = 94;

    for (int i = 1; i <= heads; i++) {
        int j = heads - i;
        if (2 * i + 4 * j == legs) {
            System.out.println("鸡的数量为 " + i + "，兔子的数量为 " + j);
        }
    }
}

上述代码枚举了所有可能的鸡和兔子的数量，当鸡和兔子的数量满足头数量和脚数量时，输出答案。

三、小结

贪心和枚举算法都是比较基础的算法，贪心算法适用于最优解可以通过每步最优解得到的问题，而枚举算法则适用于数据量较小的问题。

以上是对贪心和枚举算法的详细讲解，希望对读者有所帮助。