贪心算法

贪心算法是从问题的初始状态出发，通过若干次的贪心选择而得到的最优值（或较优
值）的一种求解问题的策略，即贪心策略。

贪心算法的特点

1. 贪心选择

所谓贪心选择是指应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后
的每一步都是当前看似最佳的选择，且这种选择只依赖于已做出的选择，不依赖于未做
出的选择。

2.最优子结构

执行算法时，每一次得到的结果虽然都是当前问题的最优解（即局部最优解），但只有
满足全局最优解包含局部最优解时，才能保证最终得到的结果是最优解。

几个简单的贪心案例

1. 最优装载问题

给 n 个物体，第 i 个物体重量为 wi，选择尽量多的物体，使得总重量不超过 C。

2.部分背包问题

有 n 个物体，第 i 个物体的重量为 wi，价值为 vi，在总重量不超过 C 的情况下让总价值
尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。

3.乘船问题

有 n 个人，第 i 个人重量为 wi。每艘船的载重量均为 C, 最多可乘两个人，求用最少的
船装载所有人的方案。

---

贪心算法的经典应用

1.选择不相交区间问题

给定 n 个开区间$[ai, bi）$, 选择尽量多个区间，使得这些区间两两没有公共点。

【思路点拨】

首先，按照结束时间 $b_1<=b_2<=…<=b_n$ 的顺序排序，依次考虑各个活动，如果没有
和已经选择的活动冲突，就选，否则就不选。

【正确性】

假设$ b_j<b_i $且$ [a_j, b_j) $、$ [a_i, b_i) $分别与之前的活动不冲突，当前选$[a_j, b_j)$,若$[a_j, b_j)$与$[ai, bi)$
不冲突，这还可以选择$[a_i, b_i)$，答案个数加一；若$[a_j, b_j)$与$[a_i, b_i)$冲突，因为$ b_j<b_i$, 所以
$[a_j, b_j)$对以后的影响更小。

【例】活动安排