17.贪心

发表于 更新于 分类于 ，

贪心

贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法策略。

重在证明

局部最优就能得到全局最优，这是一件很美好的事情，使决策变得简单易执行。

当然不是所有问题都能这样得到最优解，所以一个问题是否可以用贪心方式解决，就需要先证明贪心策略的正确性。

否定一个贪心策略很容易，找到一个反面例子。

所以尝试贪心方法的大体思路就是：

  1. 想一些拍脑门就有的局部最优策略
  2. 尝试举反例否定它们
  3. 对暂时找不到反例的思路，尝试证明正确性

比较典型的证明方法：

  • 反证法：作否定假设，则有更优解，进而推出矛盾
  • 归纳法：证\(n=1\)成立，假设\(n\)成立，推\(n+1\)成立
  • 交换论证：交换贪心方案的两个元素，答案不会变得更好，或假设任意最优解，能通过等价交换得到贪心的方案

背包类问题

例：最优装载

\(n\) 个物体，第 \(i\) 个物体重量\(w_i\)，求总重量不超过\(C\)的最多物体个数

交换论证： 假设存在最优解\(w_{s_1} \leq w_{s_2} \leq \ldots \leq w_{s_k}\)，不是轻者优先 则存在\(w_i \leq w_{s_k}\)，用\(w_i\)替换\(w_{s_k}\)仍然不会超过容量，且个数不变 不断执行该替换，总能得到轻者优先的方案

1
2
3
int ans = 0, tc = C;
std::sort(w, w + n);
for(int i = 0; i < n && tc >= w[i]; tc -= w[i ++], ans ++);

例：分数背包

有\(n\)个物品，每个物品\(i \in [1,n]\)的重量\(w_i\)，价值\(v_i\)（分别只有1个） 有一个背包可装总重不超过\(b\)的物品 求背包能装物品的最大总价值 物品可进行任意精度的分割（可以理解为金沙、液体等）

分数背包 贪心策略：“性价比”\(\frac{v_i}{w_i}\) 排序，高者优先

对0-1背包 不适用

举反例：

\(W=\{3,4,5,2\}\)，\(V=\{7,9,9,2\}\)，\(C=6\)

\(\frac{7}{3} > \frac{9}{4} > \frac{9}{5} > \frac{2}{2}\)

贪心解\(3+2=5<6\)，\(7+2=9\)

最优解\(4+2=6\)，\(9+2=11>9\)

区间类问题

例：活动选择

给出\(n\)项活动的起止时间\([s_i,f_i](i=1,2,\ldots,n)\)，最多选出多少个活动时间互不重叠(\(s_i \geq f_j\) 或 \(f_i \leq s_j\)) 例：

i 1 2 3 4 5 6 7
\(s_{i}\) 1 3 5 4 6 8 2
\(f_{i}\) 4 5 7 9 10 11 13

\(\{1,3,6\}\)是最优解之一

思考：

  • 策略1：开始时间早的优先
  • 策略2：占用时间少的优先
  • 策略3：结束早的优先

反例：

策略1：
策略2：

证明策略3结束早的优先能得到最优解——安排最多的活动

假设活动已按结束时间排序，\(f_1 \leq f_2 \leq \ldots \leq f_n\)

归纳基础：存在最优解包含可选活动里结束最早的活动。考虑多解情况，换种说法就是选最早结束的活动，不会导致得不到最优解。

交换论证，如果存在最优解不包含活动1，活动1一定可以代替该最优解中结束时间最早的那个活动，仍然是最优解

归纳论证：按此策略选了 \(k\) 个活动后，剩下的可选活动里选第 \(k+1\) 个活动时，选结束最早的那个，不会导致得不到最优解。

图中 \(S'\) 是选了 \(k\) 个活动后，剩下的不冲突的可选活动，如果把 \(S'\) 看作一个独立的活动选择问题，这个问题的最优解是 \(B\) 集合，则可以用反证法证明 \(B\) 集合和前面的 \(k\) 个活动合起来，是原来整个问题的最优解。

为了防止新手绕晕，关于这个需要反证的论断可以先跳过，读完证明后再返回来看：\(S'\) 的最优解 \(B\)，\(B \cup \{i_1,i_2,\ldots,i_k\}\) 是全局最优解，反证法证明它，可以做一个否定的假设——\(S'\) 的最优解 \(B\)，\(B \cup \{i_1,i_2,\ldots,i_k\}\) 不是全局最优解，那必然存在 \(S'\) 的另一个子集 \(B*\)，\(B* \cup \{i_1,i_2,\ldots,i_k\}\)是全局最优解（总得有个最优解吧），那\(\{i_1,i_2,\ldots,i_k\}\)都不变，只能是 \(B*\) 比 \(B\) 元素多。既然 \(B*\) 也是 \(S'\) 的子集，又比 \(B\) 元素多，那为啥 \(B*\) 不是 \(S'\) 最优解呢，这就得到矛盾了，于是推翻反证法的否定假设，原命题成立。

  • 既然\(B\)是整个问题最优解的一部分，那么第\(k+1\)个活动可以包含在\(B\)中（考虑多解问题，这里用“可以”来表述，仍然表达的是“不会导致得不到最优解”这个含义）
  • 而 \(B\) 又同时是 \(S'\) 这个独立问题的最优解，根据归纳基础——存在最优解包含可选活动里结束最早的活动
  • 那么第\(k+1\)个活动就可以是\(S'\)结束最早的活动

到这里，就说明了，不断选剩下的可选活动里结束最早的活动，能够一步步走向最优解（因为每一步都不会导致得不到最优解）。

例：最小延迟调度

给出 \(n\) 个任务的执行时长 \(t_i\) 与预期截止时间 \(d_i\) \((i=1,2,…,n)\)，求一个调度方案，使超时最严重的任务的超时时长最小。

例：\(T=\{5,8,4,10,3\}\)，\(D=\{10,12,15,11,20\}\)

调度1：顺序安排 延迟：\(0,1,2,16,10\) 最大延迟：\(16\)

调度2：截止时间安排 延迟：\(0,4,11,12,10\) 最大延迟：\(12\)

  • 策略1：按照 \(t_i\) 从小到大安排
  • 策略2：按照 \(d_i - t_i\) 从小到大安排
  • 策略3：按照 \(d_i\) 从小到大安排

反例：

  • 策略1: \(t_1=1, d_1=100, t_2=10, d_2=10\)
  • 策略2:：\(t_1=1, d_1=2, t_2=10, d_2=10\)

交换论证证明策略3：按照 \(d_i\) 从小到大安排

如果有相邻的\(2\)个任务，前一个比后一个 \(d_i\) 大，交换这两个任务，不会让延迟增加。