困难C++8 分钟2,897 字

最优子结构:贪心算法的“体检报告”

贪心算法就像一位急性子的同学,总想在每一步都选当下最好的选项,然后拍拍胸脯说:“这样走下去,结局一定最好!”但问题来了——贪心算法凭什么觉得自己能成功?​ 原因就在于它需要先通过一场“体检”。这场体检要检查的关键项目就是 最优子结构​​(Optimal Substructure)。简单说:​如果原问题的最优解,可以拆成若干个子问题的最优解来拼接,那么这个问题就拥有最优子结构​​。就像你拼乐高,车身拼得最稳,轮子装得最牢,最终整辆车才能跑得最快——每个小部分都做到最好,整体才能做到最好​​。

贪心算法之所以敢“走一步看一步”,就是因为它相信:只要当前这一步选得最好,剩下的子问题也能用同样的方法选得最好,最终拼起来就是全局最优。那么,这个“相信”到底对不对?体检报告说了算。


什么是最优子结构?——用生活小事理解

先来看两个生活中的例子,帮你快速感受什么是最优子结构。

✅ 例子1:买零食凑钱(正例)

小明有5元、10元、20元三种纸币,他想买一包15元的薯片,并且希望用最少的纸币​付钱。最优解是:一张10元 + 一张5元,共2张。 这个问题的子问题是:如果先付一张10元,剩下的5元就是子问题(用最少的纸币凑5元),而凑5元的最优解就是一张5元。把子问题的最优解(1张5元)和第一步的选择(1张10元)拼起来,就得到了原问题的最优解(2张)。 这说明凑钱问题(当纸币面额特殊时)具有最优子结构​​。

❌ 例子2:考试复习(反例)

小红期末要考数学和语文两门,她总复习时间只有2小时。数学每复习1小时能提高10分,语文每复习1小时能提高8分。她的目标是总分最高​​。 如果贪心:先选短时间内提分最多的科目——数学,复习1小时得10分;剩下1小时再复习语文得8分,总和18分。但最优方案可能是数学和语文各复习1小时?其实这里数学和语文的提分是独立的,分开最优就是整体最优,所以贪心成功。但如果换成不能同时复习两门​​,或者复习时间有重叠,贪心就可能失败。但这里只是想说明:​最优子结构要求子问题之间互不影响​​。


最优子结构和贪心选择性质——一对“好兄弟”

记住这句话:​最优子结构是贪心算法的必要条件,但不是充分条件​​。也就是说,一个问题有了最优子结构,贪心算法未必就能成功,还需要另一个条件——贪心选择性质​​。

  • 最优子结构​​:问题可以分解,子问题的最优解能拼成全局最优解。
  • 贪心选择性质​​:你选的当前这一步,就是通往全局最优的第一步。换句话说,你可以先做出一个看似局部最优的选择,然后相信剩下的子问题也能用贪心得到最优。
text
可以把贪心算法想象成:
- 最优子结构 = 你相信拼好每一块乐高后,整体模型就是最好的。
- 贪心选择性质 = 你知道当下该选哪一块乐高(比如先拼底座),而且选了这块之后,剩下的部分依然能拼成最好的模型。

反例回顾:硬币找零[1,3,4]找6元

还记得之前的硬币找零问题吗?用[1, 3, 4]三种面额的硬币找零6元,贪心会怎么做?先拿最大的4元,剩下2元,再拿两个1元,一共用了 3枚硬币 (4,1,1)。但最优解其实是两个3元硬币,只用 2枚​​。这里贪心失败了!为什么?因为问题虽然具有最优子结构​​(找零2元的最优解是2个1元,找零6元的最优解可以从子问题构造),但不具有贪心选择性质​——当前选最大的4元,并不是全局最优的第一步。所以贪心掉进了陷阱。


如何判断一个问题有没有最优子结构?

你可以用下面几个“体检指标”来检查:

  1. 分解性​​:问题能不能拆成若干个更小的同类问题?比如“找零n元”可以拆成“先选一枚硬币,然后找零剩下的钱”。
  2. 独立性​​:子问题之间不会互相影响。比如活动安排中,选了活动A后,剩下的活动只需要在A结束后的时间选,与A之前无关。
  3. 最优性​​:如果子问题不是最优的,那么拼起来的大问题也不可能是最优的。
  4. 剪贴法验证​​:假设你有一个全局最优解,把它切开,检查每一块是不是子问题的最优解。如果不是,你可以用子问题的更优解替换它,从而得到更大的全局最优——这就矛盾了,说明原假设不成立,所以子问题也一定是最优的。

对于中小学生,记住一条简单口诀​​:

如果一个问题能切成相同的更小块,并且小块的最优解拼起来就是大块的最优解,那么它就具备最优子结构。​

生活例子:收集奥特曼卡片

小明想收集一套10张不同的奥特曼卡片,他每天去抽卡,每次花1元抽一张(假设每张卡出现概率相等)。他希望能用最少的钱集齐所有卡片​​。这个问题有最优子结构吗? 拆解:先抽到一张新卡,然后剩下的问题变成集齐剩下的9张卡。如果子问题(集齐9张)的最优解是m元,那么加上第一次抽卡的钱,就是原问题的候选解。但注意,第一次抽卡可能重复,所以子问题不是完全独立——子问题的最优解依赖于当前拥有哪些卡。但整体上,这个问题的确具有最优子结构(可以用动态规划求解)。不过贪心算法(比如每次都抽最新的一张)并不一定得到最少钱数,所以它没有贪心选择性质。


常见错误:新手最容易踩的坑

错误1:以为只要问题能拆分就能用贪心

纠正​​:拆分后必须满足“子问题的最优解能拼出全局最优”。比如数字拆分问题:将正整数n拆成若干个数的和,使乘积最大。贪心地拆成尽可能多的3会得到最优吗?有时会,但需要验证。

错误2:混淆最优子结构和贪心选择性质

纠正​​:有些问题有最优子结构但没有贪心选择性质(如上面硬币找零),贪心就不行。两者缺一不可。

错误3:忘记贪心算法需要排序或选择规则

纠正​​:即使问题满足条件,贪心策略也要选对“局部最优”的标准。比如活动安排中按结束时间最早选,而不是按开始时间最早。


完整示例:活动安排问题(贪心成功的经典)

活动安排问题是贪心算法成功的典型代表。假设有多个活动,每个活动有开始时间和结束时间,一个人只能同一时间参加一个活动,问最多能参加多少个活动。 贪心策略​​:先选结束时间最早的活动,然后从剩下的活动中选与它不冲突且结束时间最早的,以此类推。

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start;   // 开始时间
    int finish;  // 结束时间
};

// 按结束时间从小到大排序
bool cmp(Activity a, Activity b) {
    return a.finish < b.finish;
}

int greedyActivity(vector<Activity>& acts) {
    sort(acts.begin(), acts.end(), cmp);  // 排序:按结束时间升序
    int count = 1;                       // 至少选第一个活动
    int last_end = acts[0].finish;       // 记录最后一个选中活动的结束时间

    for (int i = 1; i < acts.size(); i++) {
        if (acts[i].start >= last_end) { // 如果当前活动开始时间 >= 上次结束时间
            count++;
            last_end = acts[i].finish;   // 更新结束时间
        }
    }
    return count;
}

int main() {
    // 活动列表:{开始, 结束}
    vector<Activity> acts = {
        {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8},
        {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 13}
    };
    cout << "最多可以参加的活动数: " << greedyActivity(acts) << endl;
    return 0;
}

输出:

最多可以参加的活动数: 4

这个问题的最优子结构​体现在:如果你选择了第一个结束的活动,那么剩下的问题就是在该活动结束后开始的所有活动中,找最多不冲突活动;子问题的最优解加上第一个活动,就是原问题的最优解。同时,选择最早结束的活动也满足贪心选择性质​​,所以贪心能成功。


小结与相关指引

  • 最优子结构​是贪心算法的“健康指标”,它告诉我们问题可以被分解成小问题,并且小问题的最优解能组成大问题的最优解。
  • 贪心选择性质​是另一个必要条件,它告诉我们当前这一步选什么才能一步步走向最佳。
  • 如果问题同时具备这两个条件,贪心算法就能一步到位、又快又好;如果只有最优子结构而没有贪心选择性质,就需要用动态规划(比如硬币找零的通用解法)。

想更深入了解?

  • 可以看《动态规划入门》,它也是依赖最优子结构,但通过“尝试所有选择”来保证最优。
  • 再学《贪心算法的经典应用》,比如哈夫曼编码、最小生成树、最短路等,那里有更多成功例子。
  • 也可以挑战自己:想一想“排队打水”问题(每个人打水时间不同,如何安排顺序使总等待时间最短)——它有没有最优子结构?贪心又该怎么选?

记住:​下次想用贪心解决问题,先拿出“体检报告”——检查最优子结构和贪心选择性质。两项合格,大胆用;否则换思路,别硬闯!​

同类知识点