4. 贪心算法进阶：背包问题、哈夫曼编码、贪心算法的局限性
好，咱们接着聊贪心算法。上一章我们讲了贪心的基本思路——每一步都选当前最优的。听起来很简单对吧？但实际用起来，坑可不少。我这些年做调度系统，见过太多人把贪心用错地方，结果跑出来的方案还不如随机分配。
今天咱们就深入看看贪心算法的几个经典场景，顺便聊聊它的“软肋”在哪。
4.1 背包问题：贪心能搞定吗？
背包问题大家应该不陌生。给你一个容量固定的背包，一堆物品，每个物品有重量和价值，怎么装能让总价值最大？
这里有个关键分岔路：物品能不能分割。
4.1.1 分数背包问题
如果物品可以分割——比如大米、面粉这种——那就简单了。贪心策略就是：按单位价值排序，先装性价比高的。
我举个例子。假设背包容量50kg，有三种物品：
| 物品 | 重量(kg) | 总价值(元) | 单位价值(元/kg) |
|---|---|---|---|
| A | 30 | 120 | 4 |
| B | 20 | 100 | 5 |
| C | 10 | 60 | 6 |
贪心怎么选？先装C（单位价值6），再装B（单位价值5），最后装A剩下的部分。总价值 = 60 + 100 + 20×4 = 240元。这是最优解。
分数背包问题，贪心是绝对正确的。为什么？因为每一步你都在最大化“当前剩余容量”的收益，而且物品可分割，不存在“选了这个就装不下那个”的尴尬。
核心结论：分数背包问题，贪心算法就是最优解。复杂度O(n log n)，主要花在排序上。
4.1.2 0-1背包问题
但现实往往没那么美好。大多数场景下，物品是不可分割的——比如一台设备、一个零件。你要么整个拿走，要么不拿。这就是0-1背包问题。
这时候贪心就翻车了。我直接说结论：贪心算法在0-1背包问题上不保证最优。
看个反例。背包容量50kg：
| 物品 | 重量(kg) | 价值(元) | 单位价值(元/kg) |
|---|---|---|---|
| X | 50 | 100 | 2 |
| Y | 30 | 80 | 2.67 |
| Z | 20 | 70 | 3.5 |
贪心按单位价值排序：先装Z（单位价值3.5），再装Y（单位价值2.67）。但Z+Y总重量50kg，总价值150元。而如果只装X，虽然单位价值低，但总价值只有100元。嗯，这次贪心赢了。
别急，换个例子：
| 物品 | 重量(kg) | 价值(元) | 单位价值(元/kg) |
|---|---|---|---|
| P | 40 | 100 | 2.5 |
| Q | 30 | 90 | 3 |
| R | 20 | 80 | 4 |
背包容量50kg。贪心选R（单位价值4），再选Q（单位价值3），总重量50kg，总价值170元。但最优解其实是P+R，总重量60kg？等等，超了。那P+Q呢？40+30=70kg，也超了。那最优解就是R+Q=170元？不对，P单独装是100元，R单独装是80元，Q单独装是90元。R+Q=170元确实是最优。
好吧，这个例子没翻车。那我再找一个：
| 物品 | 重量(kg) | 价值(元) | 单位价值(元/kg) |
|---|---|---|---|
| A | 10 | 60 | 6 |
| B | 20 | 100 | 5 |
| C | 30 | 120 | 4 |
背包容量50kg。贪心选A（单位价值6），再选B（单位价值5），总重量30kg，总价值160元。还能装C吗？C重30kg，装不下了。总价值160元。但最优解是B+C，总重量50kg，总价值220元。贪心输了，而且输得很惨。
避坑指南：我曾经在一个仓储调度项目里，直接用贪心算法做0-1背包的货位分配。结果跑出来的方案，总价值比最优解低了将近15%。后来改成动态规划才搞定。记住：0-1背包问题，贪心只能当近似解，别指望它最优。
4.2 哈夫曼编码：贪心在数据压缩中的经典应用
说完背包，咱们聊聊哈夫曼编码。这是贪心算法在数据压缩领域最漂亮的落地之一。
哈夫曼编码解决什么问题？简单说：给你一堆字符，每个字符出现频率不同，怎么用最短的二进制串来表示它们？
贪心策略很直观：频率越高的字符，编码越短；频率越低的字符，编码越长。而且编码要满足“前缀码”性质——任何一个字符的编码，不能是另一个字符编码的前缀。
具体怎么做？我直接说步骤：
- 把所有字符按频率排好，每个字符作为一个节点
- 每次取出频率最小的两个节点，合并成一个新节点
- 新节点的频率是两个子节点频率之和
- 重复步骤2-3，直到只剩一个节点（根节点）
- 从根节点出发，左子树标0，右子树标1，路径就是编码
举个例子。假设有5个字符：A(5次)、B(4次)、C(3次)、D(2次)、E(1次)。
第一步：取最小的E(1)和D(2)，合并成新节点F(3)。
第二步：现在有A(5)、B(4)、C(3)、F(3)。取最小的C(3)和F(3)，合并成G(6)。
第三步：现在有A(5)、B(4)、G(6)。取最小的B(4)和A(5)，合并成H(9)。
第四步：现在有H(9)和G(6)。合并成根节点I(15)。
编码结果：A: 10, B: 11, C: 00, D: 010, E: 011。总长度 = 5×2 + 4×2 + 3×2 + 2×3 + 1×3 = 33位。如果用固定长度编码（3位），总长度 = (5+4+3+2+1)×3 = 45位。压缩率超过25%。
个人经验：我在做工业物联网数据采集时，传感器上报的温度、压力数据，频率分布极不均匀。用哈夫曼编码压缩后，传输量减少了将近40%。不过要注意，哈夫曼编码需要两遍扫描——第一遍统计频率，第二遍编码。实时性要求高的场景，可以考虑自适应哈夫曼编码。
4.3 贪心算法的局限性
讲了这么多，我得泼盆冷水。贪心算法虽然简单高效，但它的局限性非常明显。
第一，贪心没有“后悔药”。每一步都选当前最优，但局部最优的叠加，不一定是全局最优。就像下棋，你每一步都吃对方最大的子，但最后可能输掉整盘棋。
第二，贪心依赖问题的“贪心选择性质”。只有那些具有“最优子结构”的问题，贪心才能保证正确。比如分数背包、哈夫曼编码、最小生成树（Prim算法、Kruskal算法），这些问题的贪心选择不会影响后续选择的最优性。
第三，贪心对约束条件敏感。0-1背包问题里，物品不可分割这个约束，直接让贪心失效。我见过不少工程师，在排产调度里用贪心分配任务，结果因为任务之间有依赖关系，贪心方案导致大量等待时间。
什么时候用贪心？
- 问题规模大，需要快速得到一个“还不错”的解
- 问题本身具有贪心选择性质（需要数学证明）
- 作为更复杂算法的初始解（比如遗传算法、模拟退火）
什么时候别用贪心？
- 问题有强约束，且约束之间相互影响
- 需要精确最优解，且问题规模可控
- 问题的局部最优和全局最优有明显冲突
我举个例子。在车间调度里，有一个经典问题叫“流水车间调度”。你要安排n个工件在m台机器上加工，每个工件有固定的工艺路线。贪心策略通常是“按加工时间最短优先”，但实际效果往往很差。为什么？因为一个工件的加工时间短，不代表它后续工序不会阻塞其他工件。
我曾经在一个项目里，用贪心算法做产线排程，结果方案的总完工时间比最优解多了30%。后来改用分支定界法，虽然计算时间长了点，但方案质量明显提升。
4.4 本章知识体系
下面这张图，把本章的核心逻辑串起来了。你可以看到贪心算法在不同问题上的表现，以及它的适用边界。
这张图里，绿色分支代表贪心能完美解决的问题，红色分支代表贪心会翻车的地方，紫色部分总结了贪心的软肋。你想想看，实际工作中遇到一个问题，先别急着套贪心。先问问自己：这个问题有没有“贪心选择性质”？局部最优能不能推导出全局最优？
如果答案是否定的，那就老老实实用动态规划、分支定界，或者用贪心做个初始解，再用局部搜索去优化。别指望一把梭哈搞定所有问题。
我的建议：初学者可以先从分数背包和哈夫曼编码入手，感受一下贪心的“正确用法”。然后拿0-1背包练手，对比贪心解和最优解的差距。等你对贪心的边界有了感觉，再去处理更复杂的调度问题。
公众号:蓝海资料掘金营，微信deep3321