# 算法推理：选教材，并证明优化答案 — 学习任务单

[学习指南](https://unireadinglist.com/zh-cn/guides/algorithmic-reasoning/)

[课程专题: 算法](https://unireadinglist.com/zh-cn/subjects/computer-science/#course-algorithms)

来源核验日期: 2026-11-04

学习路线与例题编辑责任：University Reading List 编辑项目。

适合已学基础编程、递归、数据结构和离散数学的本科读者。Erickson明确假定这些准备，免费并不等于零基础编程书。下面的排程数据、任务与答案由本站创作，不是出版社原题或工作场景实证。

## 选择你的起点

- [ ] 会编程，但难以解释正确性
  能使用归纳法和基本数据结构后，以Erickson免费主线练习；先写不变量或递推式，再翻译成代码。

- [ ] 课程指定CLRS
  按第四版指定章节与伪代码约定学习。先选设计章节，不把全书的广度误当作必须逐页读完的任务。

- [ ] 难以认出问题模型
  用Skiena整理问题类型和候选方法，再回到证明型解释；实现故事不能自动证明算法正确。

## 三本书如何取舍

### Algorithms

Jeff Erickson · 1 · 2019
免费证明与设计主线

适合何时选择: 已有归纳基础，愿意自己写反例、论证和递推式。
何时另选路线: 还需要首次学习栈、散列表或编程语法。
建议阅读范围: 2019版第1–4章，然后选择第5–8章的图论内容。
局限与取舍: 作者明确列出省略的先修数据结构，也不应读者请求提供练习解答。免费正文不等于公开答案库。

#### 选书前试做

读第3–4章后，用下方五任务说明最早结束规则为何可能不能最大化报酬。
检查标准: 列出贪心方案与一个报酬更高的可行方案，核对任务ID；不能用任务个数替代报酬目标。

你的笔记:

________________________________

[官方免费阅读](https://jeffe.cs.illinois.edu/teaching/algorithms/)

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/computer-science/algorithms-erickson/)

### 算法导论

Thomas H. Cormen et al. · 4 · 2022
覆盖面广的第四版参考

适合何时选择: 课程指定CLRS，或需要跨方法一致的伪代码解释。
何时另选路线: 只需短导论，且尚不能选择阅读范围或确认先修。
建议阅读范围: 在第四版中定位Dynamic Programming和Greedy Algorithms，按需回看分析与数据结构；以手中版本目录为准。
局限与取舍: 2022年所选精装ISBN为9780262046305。教员受限资料不是自学者的公开解答权利，纸本标识也不包含所有数字产品。

#### 选书前试做

先用文字定义一个最优化子问题，再说明最优后续决策可以忽略哪些信息。
检查标准: 状态定义应决定备选项和基例；认得公式外形不等于证明最优子结构。

你的笔记:

________________________________

ISBN: 978-0-262-04630-5

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/computer-science/introduction-to-algorithms/)

### 算法设计手册

Steven S. Skiena · 3 · 2020
建模与实现伴读

适合何时选择: 需要把应用叙述转成组合问题，并比较实现方向。
何时另选路线: 希望仅凭问题目录或社区答案替代证明。
建议阅读范围: 第三版实用设计部分，尤其第10章动态规划；明确模型后再查问题目录。
局限与取舍: 作者站点的解答Wiki明确不保证社区答案正确。把答案当成待检查的论证，而不是裁决。

#### 选书前试做

将同一预约问题写成生活叙述与带权区间模型，列明兼容条件和目标。
检查标准: 每个现实条件要么进入模型，要么明确排除；熟悉的问题名称不能让约束凭空消失。

你的笔记:

________________________________

ISBN: 9783030542559

[书目信息与获取方式](https://unireadinglist.com/zh-cn/subjects/computer-science/algorithm-design-manual/)

## 检查先修准备

### 可行与最优有什么不同？

你的笔记:

________________________________

### 递推式为何需要归纳思路？

你的笔记:

________________________________

### 时间复杂度要交代什么？

你的笔记:

________________________________

## 六步学习与具体成果

- [ ] 先写模型

建议阅读范围: Erickson第0章与Skiena的建模讨论。

动手产出: 写清固定起止、半开区间、报酬、单资源及报酬和目标。

检查标准: 基本模型允许一个任务结束时立即开始下一个；没有暗含路程或准备时间。

你的笔记:

________________________________

- [ ] 反驳未经证明的捷径

建议阅读范围: Erickson第4章及CLRS的贪心讨论。

动手产出: 按最早结束运行一次，再找报酬更高的可行反例。

检查标准: 展示所选ID。反例否定特定普遍主张，不意味着所有贪心法都失败。

你的笔记:

________________________________

- [ ] 定义状态

建议阅读范围: Erickson第3章与CLRS动态规划章节。

动手产出: 按结束排序，用完整句子解释V(j)、p(j)。

检查标准: V(j)限于前j个任务；p(j)是与j兼容的最后一个前任务，没有则为0。

你的笔记:

________________________________

- [ ] 计算并说明表格

建议阅读范围: 同一动态规划范围。

动手产出: 每行比较两个选项，记录前驱并复原方案。

检查标准: 最优解要么不含j，要么包含j及兼容前缀的最优解；说明为何分类完整。

你的笔记:

________________________________

- [ ] 改变一个约束

建议阅读范围: Skiena第10章与后面的变式。

动手产出: 加入规定的准备间隔，重算兼容性后再使用递推式。

检查标准: 即使报酬和递推外形不变，p数组改变也可能使旧解不再可行。

你的笔记:

________________________________

- [ ] 提交可审查的结果

建议阅读范围: 回到最薄弱步骤对应的教材。

动手产出: 提交模型、反例、表格、复原、复杂度及边界检验。

检查标准: 另一位读者能重算目标值和可行性；给一个小程序计时不是渐近分析。

你的笔记:

________________________________

## 原创例题与解析: 原创例题：最早结束并不最大化报酬

五个虚构任务的(开始,结束,报酬)为a=(0,3,5)、b=(3,5,4)、c=(0,5,12)、d=(5,7,3)、e=(4,8,11)。一份资源只能执行不重叠任务。求最大报酬，并与最早结束法比较。

前提假设: 采用半开区间，允许结束后立即接续；时刻固定、任务不可拆分、非负报酬相加。无准备间隔、路程或不确定性。同结束时刻按b在c前排序，影响表的次序而非最优值。

你的笔记:

________________________________

## 改变假设，再做一题: 变式：任务之间必须留出间隔

保留五任务与报酬，但相邻两个被选任务之间至少留2个时间单位。最后一个任务之后无须间隔，起止时刻不能移动。重求最优值。

你的笔记:

________________________________

## 进入下一阶段之前

- 能明确目标与每一项兼容规则。
- 能说明递推并复原可行方案。
- 能改变一个假设，指出必须改变的数据或论证。

## 答案与解释

### 可行与最优有什么不同？

可行表示满足全部约束；最优需要与所有可行候选比较目标值。一个看起来不错的方案不能代替这两类一般论证。

### 递推式为何需要归纳思路？

它把已解的小问题与当前最优解连接起来，必须说明分类覆盖所有可能的最优解。

### 时间复杂度要交代什么？

定义n、输入表示与所数操作；排序、前驱计算、填表和复原分别计成本。

### 原创例题：最早结束并不最大化报酬

1. 最早结束依次选a、b、d，得5+4+3=12；可行的a、e得16，所以该贪心规则不能一般地解决带权目标。
2. 按a、b、c、d、e排序，前驱p=\[0,1,0,3,1\]。设V(0)=0，V(j)=max(V(j−1),reward(j)+V(p(j)))，分别对应不选和选j。
3. 表为V=\[0,5,9,12,15,16\]。最后一行选择e，回到前驱a，报酬11+5=16。
4. 排序与二分查前驱可用O(n log n)，填表、复原用O(n)，存储O(n)。五任务的检验与包含/排除的一般论证应分开。

最大值为16，由a与e取得；三任务贪心方案得12。最大化个数与最大化报酬是不同目标。

检验结果: 独立枚举全部32个子集，剔除不兼容者，应得到相同最优值。复原后仍须检查端点，不能只相信表里的数。

### 改变假设，再做一题: 变式：任务之间必须留出间隔

1. 兼容条件改为finish(i)+2≤start(j)，同序p=\[0,0,0,1,0\]。a能接d，却不能接b或e。
2. 新表为\[0,5,5,12,12,12\]。只选c得12；旧a、e因3+2\>4而不可行。

新最优值为12，选择c。保留递推式，重建兼容性数据；从旧报酬统一减一笔费用会变成另一模型。

检验结果: 用新兼容条件重枚举。单个任务不需末尾间隔；原最优值是放松约束模型的上界，并非这里的可行答案。

## 常见误区

### 把伪代码当证明

程序在此例返回正确值，不代表对所有输入正确。有限测试和一般论证各有作用。

### 用问题名代替模型

准备时间等条件可能破坏熟悉的归约，选择算法前要说明排除了什么。

### 复杂度只数一部分

不能漏掉排序或二次前驱扫描，再称整个实现线性；上界要对应实际实现。

## 来源与版次核验

- [Jeff Erickson: 2019 edition, prerequisites and chapter files](https://jeffe.cs.illinois.edu/teaching/algorithms/)
  作者资料核实2019版、免费正文、先修和章序。试做与数据为本站原创。

- [MIT Press: Introduction to Algorithms, fourth edition](https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/)
  MIT Press确认第四版、2022年及纸本/电子不同标识；不承诺受限教员资料。

- [Springer: The Algorithm Design Manual, third edition](https://link.springer.com/book/10.1007/978-3-030-54256-6)
  出版社支持实用设计与参考的范围区分；选书判断不是学习效果实测。

- [Author-hosted third-edition chapter and solution index](https://www.algorist.com/algowiki/)
  作者站点核实动态规划位置，并明确社区答案未获认证。

这些是本站建议的学习活动，并非大学官方作业，也不代表对每本书逐页通读。

[编辑与选书方法](https://unireadinglist.com/zh-cn/editorial/)