# Overview

部分问题的解答中，关于怎么逻辑紧密的计算近似比，我实在理解不了、解释不了；

凑合背背应付考试吧

唯一能说的：

# 顶点覆盖问题

人话翻译：对于一张图，我要找一群点$V'$。你看一条边两头不是有两个点吗，我要求对 G 图任意一条边$e$，都有$V'$ 中的一个点是 e 的两头之一

因为你想选最少的点解决问题，所以问题成本 C 就是选了多少个点，即点的数量

# 具体近似算法

随机算法，一开始$V'$ 为空，

1. 在 G 图上任取一条边 e
2. 将 e 的两端点$u,v$ 并入$V'$
3. 把$E$ 中所有以 u 为一头端点的边删掉，再把$E$ 中所有以 v 为一头端点的边删掉
4. 循环，直到 E 为空

# 时间复杂度

每次循环都会选出两点一边，所以你的算法时间复杂度为$O(C/2)$

# 近似率

对于近似率$Q(n)$，由于这是一个求最小问题，俺们的方法应该比最优方法要孬。近似比永远不小于 1，小的放分母，所以把最优$C_{opt}$ 放分母上

那咋算呢，回顾我们的随机算法，我们每轮循环会随机选一条边。到结束，我们选择所有边，是一群没有公共顶点的边，数量为 k。那我们的近似算法就选择了 2k 个点；

对于 k 个没有公共顶点的边，只要满足题设条件，那每条边至少要选一个顶点。所有满足条件的选法，其选点数量$C\ge k$，最优选法是 {所有满足条件的选法} 的一员，所以$C_{opt}\ge k$

那$\dfrac{C_{ours}}{C_{opt}}\le 2$，近似率为 2

# 集合覆盖问题

人话翻译：对于 n 个元素，我有一系列元素组成的集合$\{S\}=\{S_1,S_2,\dots,S_m\}$。这群集合并在一起覆盖了每个元素，但我嫌$m$ 太多了，我想从这$m$ 个集合中选一部分$\{S'\}$，$\{S'\}$ 含有 k 个子集。$\{S'\}$ 里所有子集并起来依然能覆盖所有元素，希望 k 最小

因为你想选最少数量的子集解决问题，所以问题成本 C 就是选了多少个子集，即子集的数量

# 具体近似算法

贪心算法，一开始$\{S\}$ 包含 m 个子集；$\{x\}$ 表示所有还没被覆盖过的元素，初始为$\{S\}$ 并起来的所有元素

1. 在${S}$ 中选择一个$S_k$，$S_k$ 中包含的元素和$\{x\}$ 交集最大；换句话，$S_k$ 能覆盖最多的还没被覆盖的元素
2. $\{S\}$ 中删除$S_k$
3. $\{x\}$ 中删除所有$S_k$ 的元素
4. 循环，直到所有元素被覆盖

# 时间复杂度

每次循环都会选出一个子集，所以你的算法时间复杂度为$O(C)$

# 近似率

对于近似率$Q(n)$，由于这是一个求最小问题，近似方法应该比最优方法要孬。近似比永远不小于 1，小的放分母，所以把最优$C_{opt}$ 放分母上

回顾我们的随机算法，假设第 k 轮循环，$\{x_k\}$ 大小为$num_k$，也就说还有$num_k$ 个元素一次都没被覆盖过

对于原$\{x\}$，$C_{opt}$ 大小的$\{S'\}$ 可以并起来全部覆盖；$\{x_k\}$ 是$\{x\}$ 的一部分，所以$\{S'\}$ 也能覆盖$\{x_k\}$，且$\{S'\}$ 中的每个子集，平均要覆盖$\{x_k\}$ 中$num_k/C_{opt}$ 个元素。

那放在这第 k 轮循环里，$\{S_k\}$ 中依然有$\{S'\}$ 中的子集$S'$；不然若没有，说明之前的循环中已经把$\{S'\}$ 取完了，那已经全覆盖了，不需要看第 k 轮循环了

子集$S’$至少要覆盖$num_k/C_{opt}$ 个$\{x_k\}$ 中的元素：因为$num_k$ 被$C_{opt}$ 个子集$S'$ 瓜分

• 要是$\{S'\}$ 在第$k$ 轮一个没少，那分母是$C_{opt}$；
• 要是第 k 轮之前有的$S'$ 被选走过了，但他们一个$\{x_k\}$ 中的元素没覆盖到，不干活；剩下的$S'$ 数量更少了，平均每个要分的$\{x_k\}$ 中的元素更多了；

在第 k 轮我们选择子集$S_k$，这个选择是贪心的，是能覆盖$\{x_k\}$ 中元素数量最多的，所以$S_k>S'$，$S_k$ 至少能覆盖$num_k/C_{opt}$ 个没覆盖过的元素，$S_k$ 覆盖新元素数$\ge num_k/C_{opt}$

那对于 k+1 轮循环，$num_{k+1}=num_k-S_k$ 覆盖新元素数，得：$num_{k+1}\le num_k\times(1-1/{C_{opt}})$

递推，得：$num_{k}\le num_0\times(1-1/{C_{opt}})^k$，$num_0$=n = 输入元素个数

令左边 < 1，经过数值计算化简，得到：

$$\dfrac{k}{t}>ln(n)$$

k 是近似算法的最小值，$k=\lceil tln(n)\rceil$，由于$C_{ours}=k$，

所以$\dfrac{C_{ours}}{C_{opt}}\le ln(n)+1/t \le ln(n)+1$

# 分组问题

其中$a_1>a_2>\dots>a_n$

人话翻译：对于 n 个元素的集合，我想切两半，使得集合的总和尽量平分到两个子集里

假设$\sum A=2L$，题目的目标将$A$ 划分为$X,Y$ 两集合，求$max(\sum X,\sum Y)$ 的最小值

所以问题成本$C$ 就是$max(\sum X,\sum Y)$，$C_{opt}=L$

# 具体近似算法

随机算法：

1. 先随机对前 m 个元素随机分配，划入 X，Y

2. 对$\{a_m+1,\dots,a_n\}$ 中的每一个$a_k$，判断$\sum X$ 和$\sum Y$，选择较小的一方，将$a_k$ 加入其中

3. 循环，直到$k=n$

# 时间复杂度

时间复杂度$O(n-m)$

# 近似率

由于这是一个求最小问题，近似方法应该比最优方法要孬。近似比永远不小于 1，小的放分母，所以把最优$C_{opt}$ 放分母上

回顾我们的随机算法，不妨假设最终$\sum X>\sum Y$，$Q(n)=\sum X/L$

考虑集合$A$ 中最后一个被分到$X$ 的元素$a_k$，它是集合 A 的第$k$ 个元素，那么元素$a_k$：

• 来自步骤 1，是随机分配时分入$X$
• 来自步骤 2，在分配$a_k$ 前，$\sum X<\sum Y$

前一种情况暂不考虑（不知道咋考虑……）

考虑后一种情况，其满足：

$$\sum X_k - a_k \le \sum Y_k\le \sum A -\sum X_k$$

其中$\sum X_k,\;\sum Y_k$ 表示划分完$a_k$ 后两子集的元素和

变形可得：

$$\sum X_k \le L + \dfrac{a_k}2$$

由$a_1>a_2>\dots>a_n$，我们可以得到：

$$\begin{align*} \sum A&\ge \sum X_k +\sum Y_k\\ &=sum(a_1,a_2,\dots,a_k)\\ &\ge (m+1)\times a_k \end{align*}$$

所以$Q(n)=\sum X/L<1+\dfrac{1}{1+m}$