贪心算法
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| greedy algorithm | 贪心算法 | tān xīn suàn fǎ |
| exchange argument | 交换论证 | jiāo huàn lùn zhèng |
现在就取最好
- 贪心算法 greedy algorithm 一步步搭解，每步取局部最优。正确性靠证明而非期望：交换论证 exchange argument 说明任何最优解都能无损变成贪心解。
{exercise:uni-cs1003-greedy}
练习
交换论证表明——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
无损地把最优换成贪心：规模不变、依然可行。
活动选择实测版
- 课程活动：(1,4)、(3,5)、(0,6)、(5,7)、(3,9)、(5,9)、(6,10)、(8,11)、(8,12)、(2,14)、(12,16)。最早结束选 (1,4)、(5,7)、(8,11)、(12,16)——四个，可证最优。
- 交换论证一遍：finish($G_1$) $\le$ finish($O_1$)，把最优首选取换成贪心首选仍可行——逐个重复，最优变成贪心、规模不变。
{exercise:uni-cs1003-activity}
练习
课程活动上最早结束法选——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
(1,4)、(5,7)、(8,11)、(12,16)——四个，可证最优。
贪心败处与 Huffman 胜处
- 硬币 1、3、4，目标 6：贪心付 4+1+1 三枚；DP 表付 3+3 两枚。交换论证失效，贪心在那里只是启发式。
- 频率 5、9、12、13、16、45 的 Huffman：反复合并最小两个——加权深度 224 位对定长码 300 位：叶子交换论证保证最小。
{exercise:uni-cs1003-huffman}
练习
硬币 1、3、4 凑 6：贪心付——枚。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
贪心取 4+1+1 三枚；DP 最优 3+3 两枚。