贪心算法：贪心策略的基本思想、活动安排问题、背包问题、最优装载问题

贪心算法，说白了就是「每次选当下最好的」。

我刚开始学数据结构时，总觉得这玩意儿太简单了——不就是每次都挑最有利的吗？后来在项目中吃过亏才明白，贪心算法的精髓不在于「贪」，而在于「怎么贪得对」。

今天咱们就把贪心策略的底裤扒干净。我会结合三个经典问题来讲：活动安排、背包问题、最优装载。每个问题我都踩过坑，咱们边聊边避雷。

贪心策略的基本思想

贪心算法的核心就一句话：局部最优 → 全局最优。

你想想看，如果你每次做决策时都选当前看起来最好的，最后的结果会不会也是最好的？

嗯，不一定。但有一类问题恰好满足这个性质。这类问题叫「贪心选择性质」和「最优子结构性质」。

我个人的习惯是：拿到一个问题，先别急着写代码。先问问自己——「如果每次都选最好的，最后能行吗？」

如果答案是肯定的，那贪心算法就是你的菜。如果不行，那就得考虑动态规划了。

活动安排问题

这是贪心算法的入门题，也是我当年面试时被问烂了的题。

问题描述：有一堆活动，每个活动有开始时间和结束时间。你只有一个会议室，问最多能安排多少个活动？

你想想看，怎么选才能安排最多？

答案是：每次选结束时间最早的那个。

为什么？因为结束时间越早，留给后面的时间就越多。这就是贪心策略——「选结束最早的」。

我曾经在做一个会议调度系统时用过这个算法。当时客户说「我要安排最多的会议」，我直接上了贪心。结果客户又加了个条件：「有些会议是VIP的，必须安排」。嗯，那就不能纯贪心了，得加优先级。

来看代码实现：

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

// 活动结构体
typedef struct {
    int start;
    int end;
} Activity;

// 按结束时间排序
int cmp(const void* a, const void* b) {
    return ((Activity*)a)->end - ((Activity*)b)->end;
}

// 贪心选择活动
int greedyActivity(Activity arr[], int n) {
    qsort(arr, n, sizeof(Activity), cmp);
    
    int count = 1;  // 第一个活动一定选
    int lastEnd = arr[0].end;
    
    for (int i = 1; i < n; i++) {
        if (arr[i].start >= lastEnd) {
            count++;
            lastEnd = arr[i].end;
        }
    }
    return count;
}

int main() {
    Activity arr[] = {{1, 3}, {2, 4}, {3, 5}, {0, 6}, {5, 7}};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("最多可安排 %d 个活动\n", greedyActivity(arr, n));
    return 0;
}

背包问题

背包问题有两个版本：0-1背包和分数背包。

贪心算法只能解决分数背包，不能解决0-1背包。这个坑我踩过，当年面试时被问到「背包问题用贪心行不行」，我脱口而出「行」，结果被面试官怼了回来。

分数背包问题：每个物品可以只拿一部分。比如一块金子，你可以切一半拿走。

贪心策略很简单：按单位重量价值排序，从高到低拿。

说白了就是「先拿最值钱的」。这个直觉是对的，因为你可以拿一部分，所以不用担心「选了这个就装不下那个」的问题。

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

typedef struct {
    int weight;
    int value;
    double ratio;  // 单位重量价值
} Item;

int cmp(const void* a, const void* b) {
    return ((Item*)b)->ratio > ((Item*)a)->ratio ? 1 : -1;
}

double fractionalKnapsack(Item items[], int n, int capacity) {
    qsort(items, n, sizeof(Item), cmp);
    
    double totalValue = 0.0;
    int currentWeight = 0;
    
    for (int i = 0; i < n; i++) {
        if (currentWeight + items[i].weight <= capacity) {
            // 全拿
            currentWeight += items[i].weight;
            totalValue += items[i].value;
        } else {
            // 拿一部分
            int remain = capacity - currentWeight;
            totalValue += items[i].ratio * remain;
            break;
        }
    }
    return totalValue;
}

最优装载问题

这个问题比前两个简单，但同样经典。

问题描述：有一艘船，载重量固定。有一堆集装箱，每个重量不同。问最多能装多少个集装箱？

你想想看，怎么装最多？

答案很简单：先装最轻的。

因为每个集装箱的价值是一样的（都是「1个」），所以为了数量最多，当然先拿轻的。

这个算法我在做物流系统时用过。当时要计算一辆卡车最多能装多少件货物，每件货物重量不同。我直接用了这个贪心策略，效率很高。

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

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int maxLoad(int weights[], int n, int capacity) {
    qsort(weights, n, sizeof(int), cmp);
    
    int count = 0;
    int currentWeight = 0;
    
    for (int i = 0; i < n; i++) {
        if (currentWeight + weights[i] <= capacity) {
            currentWeight += weights[i];
            count++;
        } else {
            break;
        }
    }
    return count;
}

知识体系总览

下面这张图把本章的核心逻辑串起来了，建议你多看两眼：

总结一下

贪心算法其实就三步：

1. 确定贪心策略——每次选什么？
2. 证明策略正确——局部最优能推出全局最优吗？
3. 实现排序+选择——代码通常很简洁

我个人觉得，贪心算法是「性价比最高」的算法之一。代码短、效率高、容易理解。但它的坑也在这里——你以为它是对的，其实它可能是错的。

所以我的建议是：用贪心之前，先想清楚两个性质。想不清楚？那就用动态规划兜底。

---

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