CSP-S 提高级 · CSP 2020 提高级第一轮 第 6 题

下列哪些问题不能用贪心法精确求解？（ ）

这题考的是贪心算法的适用边界。拿到题先想：哪些经典问题是贪心铁打的标杆（霍夫曼、最小生成树、Dijkstra），哪些看似贪心实则不行（0-1背包）。核心陷阱在于混淆‘分数背包’和‘0-1背包’，前者能贪心，后者必须DP。

学生最容易掉进‘贪心万能论’的坑，看到‘背包’二字就下意识想按性价比排序。其实只有允许切割的分数背包才能贪心，0-1背包因为物品不可分割，局部最优往往导致全局次优。另外，题目问的是‘不能’精确求解，很多同学会惯性思维选能贪心的选项，或者把霍夫曼编码误以为和背包一样有陷阱，结果选错。

考察知识点

• 贪心算法的适用条件（最优子结构 + 贪心选择性质）
• 经典问题类型的区分与反例构造
• 背包问题的分类（分数 vs 0-1）

概念定义

贪心算法：每一步都选当前看起来最好的，指望局部最优能拼成全局最优。但这招不是万能的，只有当问题同时满足最优子结构（大问题的解包含小问题的解）和贪心选择性质（当前最优选择一定在最终最优解里）时，贪心才靠谱。

命题视角

命题人最爱挖的坑就是‘看起来像贪心，其实不是’。比如背包问题，分数版（能切）和0-1版（不能切）只差一个字，贪心策略却天差地别。这道题把霍夫曼、最小生成树、Dijkstra这些贪心铁杆和0-1背包放在一起，就是要考你对‘贪心适用范围’的直觉和严谨性。

逐步推导

A. 霍夫曼编码：每次合并频率最小的两个节点，这是贪心经典案例，有最优子结构也有贪心选择性质，能精确求解。

B. 0-1背包问题：物品不能分割，必须整拿或整舍。按性价比（价值/体积）贪心选，很容易踩雷。举个反例：容量50，物品A(60,10,性价比6)、B(100,20,性价比5)、C(120,30,性价比4)。贪心先拿A和B，剩20装不下C，总价值160；但最优解是B+C=220。反例存在，说明贪心不能保证全局最优，必须用动态规划。

C. 最小生成树：Prim和Kruskal都是贪心算法，每次选最小边或离树最近的点，能精确求解。

D. 单源最短路径：Dijkstra算法每次选距离最小的未确定顶点，能精确求解（非负权图下）。

综上，只有B是贪心无法精确求解的。

避坑指南

1. 分数背包 vs 0-1背包：分数背包允许切割，贪心按性价比排序永远是最优；0-1背包不行，贪心会失败，必须用DP。题目问‘不能’，就是考你识别出0-1背包这个例外。 2. 审题陷阱：题干是‘不能’精确求解，很多同学惯性思维直接选能贪心的选项，或者把霍夫曼编码误以为和背包一样有坑，结果选错。 3. 反例思维：判断贪心是否可行，最有效的方法就是构造反例。如果找到一个场景让贪心失败，那它就不能用。

考频与趋势

贪心算法在题库中非常高频，共考过71题，覆盖2010到2026年所有考试级别，其中2026年高达24题，2024年16题，2025年12题，呈现明显上升趋势。2020年考了3题，这道题属于CSP提高级，正好对应数据中‘CSP 提高级5题’的记录。背包DP整体考过8题，2020年考了2题，说明这类‘贪心 vs DP’的辨析题在近年持续活跃。

预测

基于数据，贪心算法在2026年考得最多（24题），且CSP提高级近年稳定有题（2020年3题、2024年1题、2025年1题），未来大概率仍会高频出现‘贪心适用边界’的辨析题，尤其是背包、活动选择、区间调度等经典模型。暂无足够依据预测具体题型变化，但‘反例构造’和‘分数 vs 0-1’这类陷阱题很可能继续是命题人的最爱。