贪心算法详解（Java语言实现与实战入门）

为什么叫“贪心”？

“贪心”意味着算法在每一步都只考虑眼前利益，不考虑全局后果。虽然这种策略不能保证对所有问题都得到全局最优解，但对于某些特定问题（满足贪心选择性质和最优子结构），它能高效地找到最优解。

贪心算法的基本步骤

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的局部最优解合成原来问题的一个解。

经典案例：找零钱问题

假设你是一家商店的收银员，需要给顾客找零。硬币面额有：1元、5元、10元、25元。目标是用最少数量的硬币完成找零。

使用贪心策略：每次尽可能选择面值最大的硬币。

Java代码实现：

public class CoinChange {    public static int greedyCoinChange(int[] coins, int amount) {        // 按面值从大到小排序（本例中coins已按降序排列）        int count = 0;        for (int coin : coins) {            while (amount >= coin) {                amount -= coin;                count++;            }        }        return amount == 0 ? count : -1; // -1 表示无法找零    }    public static void main(String[] args) {        int[] coins = {25, 10, 5, 1};        int amount = 67;        int result = greedyCoinChange(coins, amount);        System.out.println("最少需要 " + result + " 枚硬币");        // 输出：最少需要 6 枚硬币（25*2 + 10*1 + 5*1 + 1*2）    }}

注意：贪心算法在此问题中有效，是因为硬币系统是“规范”的（canonical）。如果硬币面额为 {1, 3, 4}，要找6元，贪心会选4+1+1（3枚），但最优解是3+3（2枚）——此时贪心失效！因此，使用贪心前需验证问题是否适用。

另一个例子：活动选择问题

有多个活动，每个活动有开始时间和结束时间。目标是选出最多的互不冲突的活动。

贪心策略：每次选择结束时间最早的活动，这样能为后续留下最多时间。

Java实现：

import java.util.*;class Activity {    int start, end;    Activity(int s, int e) {        start = s;        end = e;    }}public class ActivitySelection {    public static List<Activity> selectActivities(Activity[] activities) {        // 按结束时间升序排序        Arrays.sort(activities, (a, b) -> Integer.compare(a.end, b.end));        List<Activity> selected = new ArrayList<>();        Activity last = activities[0];        selected.add(last);        for (int i = 1; i < activities.length; i++) {            if (activities[i].start >= last.end) {                selected.add(activities[i]);                last = activities[i];            }        }        return selected;    }    public static void main(String[] args) {        Activity[] acts = {            new Activity(1, 4),            new Activity(3, 5),            new Activity(0, 6),            new Activity(5, 7),            new Activity(8, 9)        };        List<Activity> result = selectActivities(acts);        System.out.println("最多可安排 " + result.size() + " 个活动");    }}

何时使用贪心算法？

判断一个问题是否适合用贪心策略，需满足两个条件：

• 贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来达到。
• 最优子结构：一个问题的最优解包含其子问题的最优解。

常见的适用贪心算法的问题包括：最小生成树（Kruskal、Prim）、哈夫曼编码、Dijkstra最短路径（非负权图）等。

总结

Java贪心算法是一种简单高效的算法设计思想，特别适合初学者理解算法思维。虽然它不能解决所有优化问题，但在满足特定条件下，能以较低的时间复杂度获得最优解。掌握贪心策略是迈向更高阶算法（如动态规划）的重要一步。

希望这篇算法入门教程能帮助你理解贪心算法的核心思想，并能在实际编程中灵活运用！