第四单元 贪心算法 4.1 装载问题 4.2 区间问题 4.3 删数问题 4.4 工序问题 4.5 种树问题 4.6 马的哈密尔顿链4.7 三值的排序 4.8 田忌赛马 4.9 小结

第四单元 贪心算法

以下 9 个问题都给出了相应贪心策略，但是为什么这些策略是正确的呢？请自己证明（提示：反证法）。

4.1 装载问题

(1) 简单的装载问题

【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]。求解将哪些物品装入背包可物品
数量最多。
【贪心策略】将物品重量从小到大进行排序，优先挑重量轻的装入背包。

(2) 部分背包问题

【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。每个物体可以取
走一部分，价值和重量按比例计算。求解将哪些物品装入背包可使价值总和最大。
【贪心策略】将背包按照单价（价值/重量的比值）排序。从物美价廉（单价尽可能大）的物体开始挑起，直
到背包装满或没有物体可拿。

(3) 乘船问题

【问题描述】有 n 个人，第 i 个人的重量是 wi。每艘船的最大载重量都是 C，且最多能乘两个人。用最少的船
装尽可能多的人。
【贪心策略】让最轻的人和能与他同船的最重的人乘一条船。如果办不到，就一人一条船。

 4.2 区间问题

(1) 选择不相交区间

【问题描述】数轴上有 n 个开区间(ai, bi)。选择尽量多的区间，使这些区间两两没有公共点。
【贪心策略】按 bi 从小到大的顺序排序，然后一定选择第一个区间。接下来把所有与第一个区间相交的区间排
除在外。这样在排序后再扫描一遍即可。

(2) 区间选点问题

【问题描述】数轴上有 n 个闭区间[]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含
有的点可以是同一个）。
【贪心策略】把所有区间按 从小到大排序（ 相同时，a 从大到小排序），然后一定取第一个区间的最后一
个点。

(3) 区间覆盖问题

【问题描述】数轴上有 n 个闭区间[]。选择尽量少的区间来覆盖指定线段[s, t]。

 【贪心策略】
1. 预处理：扔掉不能覆盖[s, t]的区间。