贪心算法原理与实现——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）


  贪心算法（Greedy Algorithm）是一种以 “局部最优” 推导 “全局最优” 的算法思想，其核心原理是：在问题求解的每一步决策中，都选择当前状态下看起来最优（即收益最大、成本最低或最符合某种局部准则）的选项，不考虑该决策对未来步骤的影响，通过逐步累积局部最优解，最终期望得到问题的全局最优解。

约束条件：面值固定
100
50
20
10
5
1
目标：268
→
贪心策略：优先面值最大
组合：
→
验证目标：
 
→
输出结果
最少张数：

教程目录导航

▼

一、算法原理

1.1 算法定义

  贪心算法的执行逻辑可概括为 “步步最优，累积成全局”，它不像动态规划那样考虑所有可能的子问题，也不像分治算法那样需要拆分与合并，而是沿着单一的决策路径，每一步都做出当下的最优选择，最终形成完整解。

  简单来说，贪心算法就像 “走一步看一步” 的决策方式：比如旅行时每次都选择当前最近的下一个目的地，期望最终形成最短的旅行路线；再比如找零钱时，每次都优先选择面值最大的纸币，期望用最少的纸币数量凑出目标金额。

1.2 关键特性

  1. 局部最优性：每一步决策都只关注当前状态的最优解，不回溯、不考虑后续影响，是一种 “短视” 的决策方式；
  2. 无后效性：一旦做出某一步决策，该决策就固定下来，后续的决策仅基于当前的状态，不受之前决策的反向影响；
  3. 逐步累积性：全局最优解由一系列局部最优解逐步累积而成，每一步决策都为最终解贡献一份局部最优的结果；
  4. 不保证全局最优：贪心算法的核心局限是，并非所有问题都能通过局部最优推导全局最优，仅当问题满足特定条件时，才能得到全局最优解；
  5. 高效性：贪心算法通常无需复杂的计算和存储，时间复杂度较低（多为 O (n) 或 O (n log n)），执行效率高。

1.3 核心前提

贪心算法能够得到全局最优解的两个必要前提，缺一不可：

  1. 贪心选择性质：问题的全局最优解可以通过一系列局部最优的贪心选择来获得。也就是说，每一步做出的贪心选择，都能最终导向全局最优解，无需撤销或调整之前的选择；
  2. 最优子结构性质：问题的全局最优解包含了其子问题的最优解。这是贪心算法与动态规划算法共有的性质，意味着可以通过求解子问题的最优解，逐步构建全局最优解。

只有同时满足以上两个性质的问题，才能用贪心算法求得全局最优解；若不满足，贪心算法得到的可能只是近似最优解。

二、实现步骤

要实现一个贪心算法，通常遵循以下 4 个标准步骤：

步骤 1：明确问题目标与约束条件

首先清晰界定问题的求解目标，以及问题的约束条件，这是设计贪心策略的基础。例如：

  1. 求解目标：“最少纸币数量”、“最长子序列长度”、“最大收益”等
  2. 约束条件：“纸币面值固定”、“子序列元素递增” 等

步骤 2：设计贪心策略（核心步骤）

根据问题目标，制定每一步的决策准则，即 “如何选择当前的局部最优解”。贪心策略的设计是贪心算法的灵魂，不同的贪心策略可能导致不同的结果（最优或近似最优）。例如：

  1. 找零钱问题：贪心策略是 “每次优先选择面值最大的纸币”；
  2. 活动选择问题：贪心策略是 “每次选择结束时间最早的活动”。

步骤 3：逐步执行贪心选择

按照设计好的贪心策略，依次进行每一步决策，逐步累积局部最优解，同时更新问题的当前状态（如剩余金额、剩余活动列表等），直到满足终止条件。

步骤 4：验证与输出结果

验证最终累积的解是否满足问题的目标与约束条件，若满足则输出结果；若问题不满足贪心选择性质，需评估该解是否为可接受的近似最优解。

三、优化思路

贪心算法的优化核心围绕 “贪心策略的合理性” 和 “执行效率” 展开，常见优化方向有：

  1. 优化贪心策略：通过分析问题的本质，选择更优的贪心准则，确保能得到全局最优解（如活动选择问题中，“按结束时间排序” 比 “按开始时间排序” 更合理）；
  2. 预排序优化：多数贪心算法需要先对数据进行排序（如区间问题、背包问题），选择高效的排序算法（如快速排序、归并排序），可降低整体时间复杂度；
  3. 数据结构辅助优化：利用堆（优先队列）、哈希表等数据结构，快速获取当前的局部最优解，提升决策效率（如哈夫曼编码中使用最小堆，快速获取权值最小的两个节点）；
  4. 剪枝优化：在执行贪心选择时，提前过滤掉不符合约束条件的选项，减少无效决策，提升执行速度。

四、适用场景

贪心算法适用于满足 “贪心选择性质” 和 “最优子结构性质” 的问题，常见包括：

  1. 资源分配问题（如找零钱问题、部分背包问题、任务调度问题）：需以最优方式分配有限资源，最大化 / 最小化某个目标；
  2. 区间问题（如活动选择问题、区间调度问题、区间覆盖问题）：涉及区间的选择、排序与匹配，贪心策略易生效；
  3. 编码问题（如哈夫曼编码、前缀编码）：通过贪心选择构建最优编码树，最小化编码长度；
  4. 图论问题（如最小生成树（Kruskal 算法 / Prim 算法）、最短路径（Dijkstra 算法））：图的最优路径或最优生成树求解，贪心策略可高效得到全局最优；
  5. 序列问题（如最长递增子序列（贪心 + 二分优化）、最大子数组和（简单贪心场景））：通过局部最优选择构建最优序列；
  6. 近似求解场景：对于不满足贪心前提的复杂问题（如 0-1 背包问题），贪心算法可快速得到近似最优解，满足实时性要求。

五、代码示例

下面以 “找零钱问题” 为例，展示贪心算法的实现。

问题描述：给定一组固定面值的纸币（如 [1,5,10,20,50,100]），需要给用户找零 n 元，要求使用最少数量的纸币完成找零。

算法解析

  1. 求解目标：最少纸币数量。
  2. 约束条件：纸币面值固定。
  3. 贪心策略：每次优先选择面值最大的纸币

#include <iostream>
#include <vector>

using namespace std;

// 1. 定义人民币面额（降序排列，贪心核心：优先选最大面额）
int coins[] = {100, 50, 20, 10, 5, 1};
// 面额数组的长度
int coinKind = sizeof(coins) / sizeof(coins[0]);


/**
 * 迭代实现贪心找零
 * @param remain 剩余待找零金额
 * @param changeList 存储找零组合的容器
 */
void change_iter(int remain, vector<int>& changeList)
{
    // 2. 贪心算法核心逻辑
    for (int i = 0; i < coinKind; i++) {
        int currentCoin = coins[i];
        // 只要当前面额 ≤ 剩余金额，就持续选用该面额
        while (remain >= currentCoin) {
            changeList.push_back(currentCoin);
            remain -= currentCoin;
        }
        // 提前终止循环：金额找零完成，无需遍历后续面额
        if (remain == 0) break;
    }
}

/**
 * 递归实现贪心找零
 * @param remain 剩余待找零金额
 * @param index 当前遍历的面额索引（从0开始，对应最大面额）
 * @param changeList 存储找零组合的容器
 */
void change_recu(int remain, int index, vector<int>& changeList) {
    // 递归终止条件：剩余金额为0，无需继续
    if (remain == 0) {
        return;
    }

    // 2. 贪心算法核心逻辑
    // 取出当前面额
    int currentCoin = coins[index];
    // 如果当前面额 ≤ 剩余金额，选用该面额并递归处理剩余金额
    if (remain >= currentCoin) {
        changeList.push_back(currentCoin);
        // 递归：剩余金额减少，面额索引不变（继续尝试用当前面额）
        change_recu(remain - currentCoin, index, changeList);
    } else {
        // 当前面额太大，切换到下一个更小的面额（索引+1）
        // 注意：index < coinKind-1 是防越界（最后一个面额是1，必能找零）
        if (index < coinKind - 1) {
            change_recu(remain, index + 1, changeList);
        }
    }
}

int main() {
    // 需要找零的目标金额
    int target = 268;
    // 存储最终的找零组合明细
    vector<int> changeList;

    //change_iter(target,changeList);
    change_recu(target,0,changeList);

    // 3. 输出结果
    cout << "找零 " << target << " 元，贪心算法最优解：" << endl;
    cout << "最少需要钱币数量：" << changeList.size() << " 张" << endl;
    cout << "具体找零组合：";
    for (int num : changeList) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

输出结果


找零 268 元，贪心算法最优解：
最少需要钱币数量：8 张
具体找零组合：100 100 50 10 5 1 1 1

六、优缺点

优点

  1. 高效性：时间复杂度低（多为 O (n) 或 O (n log n)），执行速度快，无需复杂的计算和存储；
  2. 简洁性：代码结构清晰，贪心策略直观易懂，开发成本低，便于维护和调试；
  3. 实用性强：适用于多种实际场景（资源分配、区间调度、图论问题等），能快速得到有效解；
  4. 近似求解能力：对于复杂问题（如 0-1 背包），虽无法得到全局最优，但能快速得到可接受的近似最优解，满足实时性要求。

缺点

  1. 不保证全局最优：仅当问题满足 “贪心选择性质” 和 “最优子结构” 时，才能得到全局最优解，否则结果为近似最优；
  2. 贪心策略设计难度高：部分问题的最优贪心策略不直观，需要深入分析问题本质，否则易得到错误解；
  3. 缺乏回溯机制：一旦做出决策无法撤销，若某一步决策失误，会导致后续所有结果偏离最优；
  4. 适用范围有限：仅适用于特定类型的问题，对依赖历史状态或需要全局规划的问题（如 0-1 背包、最长公共子序列）不适用。

七、算法对比

对比维度 贪心算法 分治算法 枚举算法
核心思想 局部最优→全局最优 分而治之（分 + 治 + 合） 穷举解空间（遍历 + 验证）
决策方式 一步一决策，无后效性 先拆分后合并，全局规划 逐一验证，无决策筛选
最优性保证 仅满足特定条件时最优 满足子问题独立时最优 解空间完整时必然最优
时间复杂度 低（O (n)/O (n log n)） 较低（O (n log n)） 高（O (n²) 及以上）
空间复杂度 低（无需额外空间） 可能需要辅助空间 低（无需额外空间）
适用场景 资源分配、区间、图论 大规模可拆分问题 小规模解空间问题

八、总结

  1. 贪心算法的核心是每一步选择局部最优，逐步累积期望得到全局最优，其关键是设计合理的贪心策略；
  2. 实现关键是 “明确问题目标、设计贪心准则、逐步执行决策”，能得到全局最优解的前提是满足 “贪心选择性质” 和 “最优子结构性质”；
  3. 经典应用包括找零钱、活动选择、哈夫曼编码、Dijkstra 算法等，适用于资源分配、区间调度等场景；
  4. 优势是高效、简洁、实用性强，劣势是不保证全局最优、贪心策略设计难度高；
  5. 与分治、递归、枚举相比，贪心算法更注重 “即时最优决策”，执行效率最高，但适用范围相对有限。

返回顶部