第15章 算法应用

本章把前面学过的算法策略放进下午题语境中使用。软件设计师下午第 4 题常以“自然语言题干 + 变量说明 + C 语言代码 + 代码填空”的形式出现，难点不是把算法从零写出来，而是读懂题干、判断策略、补上关键条件、计算复杂度和运行结果。

本章以背包问题为主线，比较贪心法、回溯法和动态规划法。学习时不要只背“某问题对应某算法”，要看清物品是否可拆分、是否要求最优解、代码里是否有回退或状态表。

学习顺序

顺序	内容	学习目标
1	背包问题概述	建立背包模型，掌握下午题阅读方法
2	背包问题（贪心法）	理解部分背包、装箱问题中的局部最优策略
3	背包问题（回溯法）	掌握 0-1 背包解空间树、约束和限界剪枝
4	背包问题（动态规划法）	掌握 0-1 背包递推式、查表和代码填空

本章主线

方法	适合场景	关键词
贪心法	部分背包、首次适宜/最佳适宜装箱	当前最优、满意解、局部判断
回溯法	0-1 背包枚举可行方案	选或不选、搜索树、回退、剪枝
动态规划法	0-1 背包求最优值	最优子结构、递推式、二维数组、查表

下午题拿分策略

分值来源	常见分值	复习抓手
代码填空	8 到 10 分	看变量说明、循环边界、递推式、上下文对称结构
算法策略判断	约 2 分	回退看回溯，二分看分治，表格中间结果看动态规划，当前最优看贪心
时间复杂度	约 2 分	先找循环层数，再看递归/二分/状态表规模
实例运行结果	约 3 分	按题干策略手工模拟，不按自己习惯改算法

判断算法策略的顺序

flowchart TD
  A["读题干和代码"] --> B{"有探索和回退?"}
  B -- 是 --> C["回溯法"]
  B -- 否 --> D{"有明显二分/子问题合并?"}
  D -- 是 --> E["分治法"]
  D -- 否 --> F{"有递推式和中间数组?"}
  F -- 是 --> G["动态规划法"]
  F -- 否 --> H{"每步按当前最优选择?"}
  H -- 是 --> I["贪心法"]
  H -- 否 --> J["结合题干继续判断"]

本章提醒

背包问题里最容易误会的是“最优子结构”和“贪心”。0-1 背包确实有最优子结构，所以可以用动态规划；但它通常不具备简单的贪心选择性质，所以“按价值最大”或“按单位价值最大”不一定保证全局最优。部分背包可以拆分，单位价值贪心才成立。

本章小结

• 下午算法应用题要从题干和代码共同找答案。
• 部分背包可用单位价值贪心，0-1 背包通常用回溯或动态规划。
• 回溯看“试探、剪枝、回退”，动态规划看“状态、递推、查表”。