一、贪心算法概述

1.1 基本定义

贪心算法（Greedy Algorithm）是一种在每一步决策过程中，都做出当前局部最优选择，最终希望通过一系列局部最优解，得到问题全局最优解的算法思想。

简单理解：走一步看一步，只选择眼前最优，不回溯、不后悔。

1.2 核心特性

1. 无后效性：当前选择只影响当前状态，后续决策不会改变已经做出的选择。

2. 局部最优推导全局最优：只有问题满足特定性质时，贪心才能得到正确结果。

3. 高效简洁：时间复杂度通常为 O (n) 或 O (n log n)，实现简单、运行速度快。

1.3 算法适用前提

1. 贪心选择性质：全局最优解可以通过一系列局部最优选择逐步构造。

2. 最优子结构性质：问题的最优解包含其子问题的最优解。

注意：不满足以上两个条件时，贪心算法不能保证结果正确。

1.4 优缺点

• 优点：实现简单、效率高、代码量小，易于理解和调试。

• 缺点：适用场景有限，必须提前验证问题是否满足贪心性质。

---

二、贪心经典应用（C 语言实现・带详细注释）

应用 1：分饼干

题目描述

每个孩子有一个胃口值，每个饼干有固定大小。只有当饼干大小 ≥ 孩子胃口时，孩子才能被喂饱。请计算最多能喂饱多少个孩子。

贪心策略

将孩子胃口数组和饼干大小数组均按从小到大排序，用最小够用的饼干喂饱当前胃口最小的孩子，最大化饼干的利用率，从而喂饱更多孩子。

C 语言代码（可直接复制运行）

#include <stdio.h>
#include <stdlib.h>

// qsort排序比较函数：实现数组从小到大排序
int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

/*
 * 函数功能：计算最多能喂饱的孩子数量
 * 参数说明：
 * g: 孩子胃口数组
 * gSize: 孩子的总数量
 * s: 饼干大小数组
 * sSize: 饼干的总数量
 * 返回值：最多能喂饱的孩子数量
 */
int findContentChildren(int *g, int gSize, int *s, int sSize) {
    // 1. 对孩子胃口数组升序排序
    qsort(g, gSize, sizeof(int), cmp);
    // 2. 对饼干大小数组升序排序
    qsort(s, sSize, sizeof(int), cmp);

    int i = 0;  // 指向当前待喂饱的孩子
    int j = 0;  // 指向当前正在尝试使用的饼干

    // 遍历所有孩子和饼干，直到其中一方遍历完毕
    while (i < gSize && j < sSize) {
        // 当前饼干能喂饱当前孩子，切换到下一个孩子
        if (s[j] >= g[i]) {
            i++;    // 孩子数量+1（已喂饱）
        }
        j++;        // 无论饼干是否可用，都切换到下一块饼干
    }

    return i;   // 已喂饱的孩子总数
}

// 主函数：测试代码
int main() {
    int g[] = {1, 2, 3};    // 孩子胃口数组
    int s[] = {1, 1};       // 饼干大小数组
    // 调用函数，输出结果
    printf("最多能喂饱的孩子数量：%d\n", findContentChildren(g, 3, s, 2));
    return 0;
}

应用 2：跳跃游戏 II

题目描述

给定一个非负整数数组 nums，数组中每个元素表示在当前位置可以跳跃的最大长度。初始位置在数组的第一个元素处，求到达数组最后一个元素的最少跳跃次数。

贪心策略

在当前可跳跃的范围内，记录能到达的最远位置；当到达当前跳跃的边界时，必须跳跃一次，并将边界更新为之前记录的最远位置，以此保证跳跃次数最少。

C 语言代码（可直接复制运行）

#include <stdio.h>

/*
 * 函数功能：计算到达数组末尾的最少跳跃次数
 * 参数说明：
 * nums: 存储每个位置跳跃能力的数组
 * numsSize: 数组的长度
 * 返回值：最少跳跃次数
 */
int jump(int *nums, int numsSize) {
    // 数组长度≤1时，无需跳跃，直接返回0
    if (numsSize <= 1) return 0;

    int jumps = 0;     // 记录总跳跃次数
    int curEnd = 0;    // 当前跳跃所能到达的边界
    int maxReach = 0;  // 当前范围内能到达的最远位置

    // 遍历至倒数第二个元素（到达最后一个元素无需跳跃）
    for (int i = 0; i < numsSize - 1; i++) {
        // 更新当前范围内能到达的最远位置
        if (i + nums[i] > maxReach) {
            maxReach = i + nums[i];
        }

        // 到达当前跳跃边界，必须跳跃一次
        if (i == curEnd) {
            jumps++;                // 跳跃次数+1
            curEnd = maxReach;      // 更新新的跳跃边界
            // 若新边界已能到达终点，提前退出循环
            if (curEnd >= numsSize - 1) {
                break;
            }
        }
    }

    return jumps;
}

// 主函数：测试代码
int main() {
    int nums[] = {2, 3, 1, 1, 4};  // 跳跃能力数组
    // 调用函数，输出结果
    printf("到达数组末尾的最少跳跃次数：%d\n", jump(nums, 5));
    return 0;
}

应用 3：区间调度（最多不重叠区间）

题目描述

给定若干个区间，每个区间包含起点和终点，选择最多数量的互不重叠区间（区间端点可以重合，不算重叠）。

贪心策略

将所有区间按结束时间升序排序，每次选择结束时间最早的区间，这样可以为后续区间预留更多的空间，从而选择更多的不重叠区间。

C 语言代码（可直接复制运行）

#include <stdio.h>
#include <stdlib.h>

// 定义区间结构体：包含起点和终点
typedef struct {
    int start;  // 区间起点
    int end;    // 区间终点
} Interval;

// 排序比较函数：按区间结束时间升序排序
int cmp(const void *a, const void *b) {
    Interval *x = (Interval *)a;
    Interval *y = (Interval *)b;
    return x->end - y->end;
}

/*
 * 函数功能：计算最多能选择的不重叠区间数量
 * 参数说明：
 * intervals: 区间数组
 * intervalsSize: 区间的总数量
 * 返回值：最多不重叠区间数量
 */
int eraseOverlapIntervals(Interval *intervals, int intervalsSize) {
    // 区间数量为0时，返回0
    if (intervalsSize == 0) return 0;

    // 按区间结束时间升序排序
    qsort(intervals, intervalsSize, sizeof(Interval), cmp);

    int count = 1;               // 至少能选择一个区间
    int lastEnd = intervals[0].end;  // 上一个选中区间的结束时间

    // 遍历所有区间，筛选不重叠的区间
    for (int i = 1; i < intervalsSize; i++) {
        // 当前区间起点≥上一个区间终点，说明不重叠，可选择
        if (intervals[i].start >= lastEnd) {
            count++;                // 选中区间数量+1
            lastEnd = intervals[i].end;  // 更新上一个区间的结束时间
        }
    }

    return count;
}

// 主函数：测试代码
int main() {
    // 定义区间数组
    Interval arr[] = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    // 调用函数，输出结果
    printf("最多能选择的不重叠区间数量：%d\n", eraseOverlapIntervals(arr, 4));
    return 0;
}

应用 4：硬币找零（标准币值）

题目描述

给定标准币值 {25, 10, 5, 1}，凑出指定金额 amount，求使用的最少硬币数量。

贪心策略

每次优先使用面值最大的硬币，尽可能用最大面值的硬币凑出金额，减少硬币的使用数量，从而得到最少硬币数。

C 语言代码（可直接复制运行）

#include <stdio.h>

/*
 * 函数功能：用最少硬币凑出指定金额
 * 参数说明：
 * amount: 需要凑出的金额
 * 返回值：最少硬币数量
 */
int coinChange(int amount) {
    // 标准币值：按面值从大到小排列
    int coins[] = {25, 10, 5, 1};
    int count = 0;  // 记录硬币总数

    // 遍历所有面值，从大到小使用硬币
    for (int i = 0; i < 4; i++) {
        // 尽可能多地使用当前面值的硬币
        while (amount >= coins[i]) {
            count++;        // 硬币数量+1
            amount -= coins[i];  // 扣除当前面值的金额
        }
    }

    return count;
}

// 主函数：测试代码
int main() {
    int amount = 41;  // 需要凑出的金额
    // 调用函数，输出结果
    printf("凑出%d分钱最少需要的硬币数量：%d\n", amount, coinChange(amount));
    return 0;
}

---

应用 5：哈夫曼编码

题目描述

根据字符的出现频率，构建哈夫曼树，生成最优前缀编码（哈夫曼编码），使所有字符的总编码长度最小。

贪心策略

每次选择频率最小的两个节点进行合并，生成一个新的父节点（父节点频率为两个子节点频率之和），重复此过程，直至所有节点合并为一棵哈夫曼树，最终生成最优编码。

C 语言代码（可直接复制运行）

#include <stdio.h>
#include <stdlib.h>

// 定义哈夫曼树节点结构体
typedef struct Node {
    char ch;          // 存储的字符
    int freq;         // 字符的出现频率
    struct Node *left;   // 左孩子节点
    struct Node *right;  // 右孩子节点
} Node;

/*
 * 函数功能：创建一个新的哈夫曼树节点
 * 参数说明：
 * ch: 节点存储的字符
 * freq: 字符的出现频率
 * 返回值：新创建的节点指针
 */
Node *newNode(char ch, int freq) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = node->right = NULL;  // 初始时左右孩子为空
    return node;
}

/*
 * 函数功能：递归打印哈夫曼编码
 * 参数说明：
 * root: 哈夫曼树的根节点
 * code[]: 存储编码路径（0表示左子树，1表示右子树）
 * top: 当前编码的长度
 */
void printCodes(Node *root, int code[], int top) {
    // 左子树：编码记为0，递归打印左子树
    if (root->left) {
        code[top] = 0;
        printCodes(root->left, code, top + 1);
    }
    // 右子树：编码记为1，递归打印右子树
    if (root->right) {
        code[top] = 1;
        printCodes(root->right, code, top + 1);
    }
    // 叶子节点：输出字符及其对应的哈夫曼编码
    if (!root->left && !root->right) {
        printf("%c: ", root->ch);
        for (int i = 0; i < top; i++) {
            printf("%d", code[i]);
        }
        printf("\n");
    }
}

// 主函数：测试代码（构建简易哈夫曼树并打印编码）
int main() {
    // 构建简易哈夫曼树（根节点频率为10，左右孩子频率均为5）
    Node *root = newNode('#', 10);  // 根节点（无实际字符，用#表示）
    root->left = newNode('a', 5);   // 左孩子：字符a，频率5
    root->right = newNode('b', 5);  // 右孩子：字符b，频率5

    int code[100];  // 存储哈夫曼编码
    printf("哈夫曼编码结果：\n");
    printCodes(root, code, 0);  // 打印编码
    return 0;
}

应用 6：最小生成树（Kruskal 算法）

题目描述

给定一个带权无向图，求权值总和最小的生成树（生成树需连通所有顶点，且无环，边数为顶点数 - 1）。

贪心策略

将图中所有边按权值升序排序，依次选择边，若加入该边后不会形成环，则保留该边；重复此过程，直至选择的边数为顶点数 - 1，此时得到的就是最小生成树。

C 语言代码（可直接复制运行）

#include <stdio.h>
#include <stdlib.h>

// 定义边结构体：包含两个顶点和边的权值
typedef struct {
    int u;  // 顶点1
    int v;  // 顶点2
    int w;  // 边的权值
} Edge;

int parent[100];  // 并查集：存储每个顶点的父节点，用于判断环

/*
 * 函数功能：并查集查找根节点（带路径压缩，提高效率）
 * 参数说明：
 * x: 需要查找根节点的顶点
 * 返回值：顶点x的根节点
 */
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);  // 路径压缩
    }
    return parent[x];
}

// 排序比较函数：按边的权值升序排序
int cmp(const void *a, const void *b) {
    Edge *x = (Edge *)a;
    Edge *y = (Edge *)b;
    return x->w - y->w;
}

/*
 * 函数功能：Kruskal算法求最小生成树总权值
 * 参数说明：
 * edges: 图的边数组
 * n: 图的顶点数量
 * e: 图的边数量
 * 返回值：最小生成树的总权值
 */
int kruskal(Edge edges[], int n, int e) {
    // 初始化并查集：每个顶点的父节点是自身
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    // 按边的权值升序排序
    qsort(edges, e, sizeof(Edge), cmp);

    int sum = 0;    // 最小生成树的总权值
    int count = 0;  // 已选择的边数

    // 遍历所有边，筛选符合条件的边
    for (int i = 0; i < e; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;

        // 若两个顶点不在同一集合，加入边不会形成环
        if (find(u) != find(v)) {
            parent[find(u)] = find(v);  // 合并两个集合
            sum += w;                   // 累加边的权值
            count++;                    // 已选择边数+1

            // 最小生成树边数为n-1，满足条件则退出
            if (count == n - 1) {
                break;
            }
        }
    }

    return sum;
}

// 主函数：测试代码
int main() {
    // 定义图的边数组（3个顶点，3条边）
    Edge edges[] = {{1, 2, 1}, {1, 3, 3}, {2, 3, 1}};
    int n = 3;  // 顶点数量
    int e = 3;  // 边数量
    // 调用函数，输出结果
    printf("最小生成树的总权值：%d\n", kruskal(edges, n, e));
    return 0;
}

---

三、总结

贪心算法 = 每一步局部最优，不回溯。

1. 必须满足：贪心选择性质 + 最优子结构。

2. 经典应用：

   1. 分饼干

   2. 跳跃游戏 II

   3. 区间调度

   4. 硬币找零

   5. 哈夫曼编码

   6. 最小生成树 Kruskal

3. 优点：代码简洁、效率高；缺点：适用场景有限。