贪心算法入门：从直觉到严谨

大家好，我是老张。今天咱们聊聊贪心算法。说实话，我刚入行那会儿，觉得这玩意儿挺玄乎的——明明每一步都选当前最优，最后居然能得出全局最优？这不科学啊！后来做项目多了才发现，贪心算法其实很符合人类的直觉思维。

你想想看，生活中我们做决策时，是不是也经常用贪心策略？比如去超市买东西，你肯定先挑最想吃的；赶时间出门，肯定先穿最方便的衣服。嗯，贪心算法就是这么回事——每一步都做出当前看起来最好的选择。

贪心算法的基本思想

说白了，贪心算法就是「只顾眼前，不管未来」。它不回溯，不纠结，一条道走到黑。这种策略在特定问题上非常高效，时间复杂度通常很低。

我个人的理解是：贪心算法像是一个「近视眼」的决策者。它看不到远处的风景，但每一步都踩在最稳的石头上。如果这条路本身设计得好（满足贪心选择性质），那它就能走到终点。

贪心算法的适用条件

不是所有问题都能用贪心算法。我踩过不少坑，曾经在一个调度问题上硬套贪心，结果跑出来的方案比随机还差。后来才明白，贪心算法需要满足两个关键条件。

最优子结构

一个问题的最优解包含其子问题的最优解。听起来有点绕？我举个例子：

假设你要从北京去上海，最短路径经过济南。那么从北京到济南这一段，也必须是北京到济南的最短路径。否则，你完全可以换一条更短的北京→济南路线，整体路径就更短了——这就矛盾了。

我在项目中遇到过类似场景：做物流路径规划时，如果子路径不是最优的，整个配送方案就会出问题。所以，最优子结构是贪心的基础。

贪心选择性质

这个条件更微妙。它要求：通过局部最优选择，能够推导出全局最优解。也就是说，你不需要考虑未来的选择，当前这一步选最好的，后面自然水到渠成。

我曾经犯过一个错误：在背包问题里用贪心，按价值密度排序选物品。结果发现，因为背包容量限制，贪心选出来的组合反而不如某些「次优」组合。这就是因为背包问题不满足贪心选择性质。

经典案例：活动选择问题

这是贪心算法的入门题，也是我当年学算法时第一个看懂的案例。

问题描述：有一系列活动，每个活动有开始时间和结束时间。你只能同时参加一个活动，问最多能参加多少个？

贪心策略很简单：每次选结束时间最早的活动。为什么？因为结束早，留给后面的时间就多。

// 活动选择 - 贪心算法
function activitySelection(activities) {
    // 按结束时间排序
    activities.sort((a, b) => a.end - b.end);
    
    let count = 1;
    let lastEnd = activities[0].end;
    let selected = [activities[0]];
    
    for (let i = 1; i < activities.length; i++) {
        if (activities[i].start >= lastEnd) {
            count++;
            selected.push(activities[i]);
            lastEnd = activities[i].end;
        }
    }
    
    return { count, selected };
}

// 示例
const acts = [
    { start: 1, end: 4 },
    { start: 3, end: 5 },
    { start: 0, end: 6 },
    { start: 5, end: 7 },
    { start: 8, end: 9 }
];
console.log(activitySelection(acts));
// 输出: { count: 3, selected: [1-4, 5-7, 8-9] }

你看，代码很简洁。时间复杂度主要花在排序上，O(n log n)。我建议你手写一遍这个算法，感受一下贪心的「爽感」。

经典案例：找零问题

这个更贴近生活。你去便利店买东西，收银员找零时，是不是先拿大面额的？这就是贪心。

问题：给定面额 [25, 10, 5, 1] 美分，找零 63 美分，用最少的硬币数。

贪心策略：每次选不超过剩余金额的最大面额。

function coinChange(coins, amount) {
    // 假设 coins 已按降序排列
    let result = [];
    let remaining = amount;
    
    for (let coin of coins) {
        while (remaining >= coin) {
            result.push(coin);
            remaining -= coin;
        }
    }
    
    return result;
}

console.log(coinChange([25, 10, 5, 1], 63));
// 输出: [25, 25, 10, 1, 1, 1] 共6枚

经典案例：最小生成树

这是图论里的经典问题。给你一个带权连通图，找一棵树连接所有顶点，且总权重最小。

两个经典算法：Prim 和 Kruskal。它们都是贪心思想，但策略不同。

Prim 算法

从一个顶点开始，每次选一条连接「已选顶点集」和「未选顶点集」的最小边。说白了，就是「慢慢往外扩张」。

function prim(graph, start) {
    const n = graph.length;
    const visited = new Array(n).fill(false);
    const minDist = new Array(n).fill(Infinity);
    const parent = new Array(n).fill(-1);
    
    minDist[start] = 0;
    
    for (let i = 0; i < n; i++) {
        // 找未访问中距离最小的顶点
        let u = -1;
        for (let j = 0; j < n; j++) {
            if (!visited[j] && (u === -1 || minDist[j] < minDist[u])) {
                u = j;
            }
        }
        
        visited[u] = true;
        
        // 更新邻居的距离
        for (let v = 0; v < n; v++) {
            if (graph[u][v] !== 0 && !visited[v] && graph[u][v] < minDist[v]) {
                minDist[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }
    
    return parent;
}

Kruskal 算法

这个更直接：把所有边按权重排序，从小到大选边，只要不形成环就加入。我特别喜欢这个算法，因为它思路清晰，实现起来也简单。

function kruskal(edges, n) {
    // edges: [{u, v, weight}]
    edges.sort((a, b) => a.weight - b.weight);
    
    const parent = Array.from({length: n}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    function union(x, y) {
        parent[find(x)] = find(y);
    }
    
    const result = [];
    for (let edge of edges) {
        if (find(edge.u) !== find(edge.v)) {
            result.push(edge);
            union(edge.u, edge.v);
        }
    }
    
    return result;
}

知识体系总览

下面这张图帮你理清本章的核心脉络：

这张图把本章的知识点串起来了。从上到下，从思想到条件再到案例，一目了然。

小结

贪心算法其实不难，难的是判断一个问题能不能用贪心。我个人的经验是：先试试贪心，如果发现反例，再考虑动态规划。很多初学者一上来就套 DP，反而把简单问题复杂化了。

记住三个要点：

• 贪心是「短视」的，但有时短视反而高效
• 最优子结构是前提，贪心选择性质是关键
• 活动选择、找零、最小生成树是三个经典模板

好了，这一章就到这里。代码我都贴出来了，建议你动手跑一跑。遇到问题别慌，多想想「如果这一步选最优，后面会怎样」——这就是贪心的思维方式。

---

公众号:蓝海资料掘金营，微信deep3321