【算法笔记】贪心算法

一、什么是贪心算法？

贪心算法是一种在每一步选择中都采取当前看起来最优（最“贪心”）的策略，从而希望得到全局最优解的算法设计思想。

• 核心思想：每一步都做出局部最优选择，不回退。
• 适用场景：问题具有最优子结构且满足贪心选择性质 —— 即局部最优可以导出全局最优。

---

二、贪心算法的典型流程

1. 排序/预处理：对待选元素进行必要的排序或组织。
2. 局部选择：按照某种规则（如最大收益、最小代价等）依次选取元素。
3. 可行性检验：检查当前选择是否满足约束。
4. 解的构造：在每次选择的基础上逐步构建最终解。

---

三、经典例题回顾

1. 活动选择问题

• 题目：有 $n$ 个活动，每个活动有开始时间 $s_i$ 和结束时间 $f_i$，要求选出最多互不冲突的活动集合。
• 贪心策略：按活动结束时间从小到大排序，每次选取结束最早且与当前已选活动不冲突的活动。

2. 分数背包问题（Fractional Knapsack）

• 题目：有 $n$ 件物品，每件物品重量 $w_i$，价值 $v_i$，背包容量 $W$。物品可分割装入。
• 贪心策略：按单位重量价值 $\frac{v_i}{w_i}$ 从大到小装入；装不下时装入尽可能多的部分。

3. 最小生成树（Kruskal 算法）

• 题目：给定带权无向图，求一棵权值之和最小的生成树。
• 贪心策略：对所有边按权值从小到大排序，依次加入不会形成环的最小边。

---

四、实战题目 —— 给 $n$ 个国家加税

4.1 题目描述

• 有 $n$ 个国家，初始关税税率均为 100%。
• 对第 $i$ 个国家，加税一次可将其税率提升 $p_i\%$（即税率从上一次的值再加上 $p_i$ 百分点）。
• 允许一共进行 $k$ 次加税操作，每次只能选择一个国家进行一次加税。
• 求经过 $k$ 次加税后，所有国家税率的累乘（乘积）的最大值。

示例

输入：n = 3, p = [2, 5, 3], k = 4  
输出：最大乘积（按百分比计算）

4.2 贪心思路分析

收益定义

• 对第 $i$ 个国家当前税率 $t_i$（最开始 $t_i=100\%$）再加一次 $p_i\%$，其新的税率为 $t_i+p_i$。
• 在乘积中，相当于将当前乘积乘以 $\frac{t_i+p_i}{t_i}$，因此这次操作对总乘积的放大倍数为：

$r_i=\frac{t_i+p_i}{t_i}=1+\frac{p_i}{t_i}$

• 要使乘积最大，每次都应选择能带来最大放大倍数 $r_i$ 的国家。

优先队列实现

• 使用一个最大堆（priority_queue）存储每个国家当前可获得的放大倍数 $r_i$。
• 每次取出堆顶（$r_i$ 最大的国家），实施一次加税：
  1. 更新该国家税率：$t_i\leftarrow t_i+p_i$。
  2. 计算新的放大倍数：$r_i\leftarrow 1+\frac{p_i}{t_i}$。
  3. 将更新后的 $r_i$ 重新压入堆中。
• 重复上述过程 $k$ 次，结束后遍历所有国家税率，计算乘积。

---

4.3 代码示例（C++）

#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, k;cin >> n >> k;vector<double> p(n), t(n, 100.0);for (int i = 0; i < n; i++) {cin >> p[i];}// 优先队列：pair<放大倍数, 国家索引>auto cmp = [](const pair<double,int>& a, const pair<double,int>& b) {return a.first < b.first;};priority_queue<pair<double,int>, vector<pair<double,int>>, decltype(cmp)> pq(cmp);// 初始化for (int i = 0; i < n; i++) {double r = 1.0 + p[i] / t[i];pq.push({r, i});}// 执行 k 次加税while (k--) {auto [r, i] = pq.top(); pq.pop();t[i] += p[i];r = 1.0 + p[i] / t[i];pq.push({r, i});}// 计算累乘结果double ans = 1.0;for (double tax : t) {ans *= tax / 100.0;}cout << fixed << setprecision(6) << ans << "\n";return 0;
}

---

4.4 复杂度分析

• 每次操作：弹出堆顶 + 插入堆顶，各 $O(\log n)$。
• 总共 $k$ 次操作，时间复杂度为：$O(k\log n)$。
• 空间复杂度：需要存储 $n$ 个国家的信息，为 $O(n)$。

---

五、更多贪心练习题推荐

1. 区间染色问题：给定区间集合，最少使用多少种颜色使重叠区间不同色？
2. 跳跃游戏 II：每格有最大跳跃长度，求最少跳跃次数到达末尾。
3. 分配饼干：孩子有满足度，饼干有大小，如何让最多孩子满足？
4. 连通区间合并：给一堆区间，合并所有重叠区间，输出不重叠区间集合。

---

六、小结

• 贪心算法以“当前最优选择”逐步构建解，适合于“最优子结构”且满足“贪心选择性质”的问题。
• 真正的难点在于如何证明局部最优能导出全局最优，以及如何设计合适的贪心策略。
• 通过上述“加税”题，以及经典例题的练习，可以加深对贪心算法的理解与应用。