一些概念
介绍背包问题之前，先说明几个概念。
标准时间复杂度：在标准时间复杂度中，输入规模的定义为：保存输入数据所需要的bit位数。举个例子，在排序算法中，输入是32-bit整数的数组，那么输入规模就是$32n$，$n$ 是指数组中元素的个数。
多项式时间：对于一个问题，在输入规模为$x$ 的情况下，如果一个算法能够在 $O(x^k)$ 时间内解决此问题，则我们称此算法是多项式时间的，其中$k$ 为常数。
在一些问题中，标准定义下的多项式时间与传统的多项式时间是相同的。如冒泡排序中传统时间复杂度为 $O(n^2) $ ，对于$n$ 个元素，它的输入规模是 $32n$，因此标准定义下的时间复杂度为 $O((x/32)^2) = O(x^2)$ 。
但在一些问题中则不同, 考虑判断一个整数是否为素数的算法, 设输入的整数为 $n$, 我们可以简单得到一个时间复杂度为 $O(n^k)$ 的算法。然而, 保存一个整数需要的 bit 位数是 $x = \log n$ , 在标准时间复杂度中, 算法的复杂度变成了 $ (2^x)^k = 2 ^{xk} $, 是指数时间复杂度。
伪多项式时间复杂度 (PPTAS (Pseudo-polynomial time approximation scheme)) : 一个算法的传统时间复杂度是多项式时间的，而标准时间复杂度不是多项式时间的。
接下来我们考虑一个 NP-hard 问题 $\cal I$ 的近似算法 $\cal A$, $\epsilon $ 表示该算法的误差参数 $ \epsilon = \frac{\vert OPT(\cal I) -A(\cal I)\vert }{OPT(\cal I)} $
多项式时间近似算法 (PTAS (Polynomial time approximation scheme)) : 对于每一个固定的 $\epsilon >0$ ，算法 $\cal A$ 的运行时间以实例 $\cal I$ 的规模的多项式为上界。
然而有多项时间近似算法并不一定就有很好的应用, 因为很多算法都是$1/ \epsilon $ 的指数时间算法,如 $ O(n^{1/\epsilon})$ , 当我们希望误差小于 1% 时, 算法复杂度可能高达 $ O(n^{100})$ , 因此提出一个更强的要求:
完全多项式时间近似算法 (FPTAS (Fully polynomial time approximation scheme)): 算法 $\cal A$ 的运行时间以实例 $\cal I$ 的规模和 $1/ \epsilon $ 的多项式为上界。即算法复杂度为 $ O(n^k / \epsilon ^ m)$
背包问题
问题: 给定$n$个物品，第 $i$ 个物体大小为 $s_i$，价值为 $v_i$ ， 背包大小为 K , 找到物品的集合使得背包内物品的价值最大。
整数规划:
我们已经知道背包问题的整数规划形式: 记有 $n$ 个物品，第 $i$ 个物体大小为 $s_i$，价值为 $v_i$ ， 背包大小为 K ， $ x_i = 1 $ 表示选中该物体， $x_i = 0$ 则不选。背包问题的整数规划为：
$$
\max \sum_{i =1}^n v_i x_i \quad\
s.t. \sum_{i=1}^n s_i x_i \le C\
x_i \in {0,1}
$$
贪心算法
背包问题最合理的贪心算法是根据物品的单位价值 $ {v_i}/{s_i}$ 对物品进行排序, 从单位价值最大的物品开始选取直到无法放入背包。
这个算法的近似比是无穷大的: 我们考虑三个解:
- 将整数规划放松为线性规划的最优解 $OPT_{LP} (\cal I)$ : 可以简单得到, 线性规划的最优解会去单位价值最大的前 $m$ 个物品为 1, 下一个物品为小数 (或0) : 线性规划总能使背包装满, 选择单位价值最大的物品可以是在一定的空间内总价值最大。记前 $m$ 个物品的总价值为 $\alpha$ , 下一个物品的价值为 $\beta$, $OPT_{LP} (\cal I) \le \alpha + \beta$
- 贪心算法的解 $Greedy (\cal I) $: 前 $m$ 个物品也会被取到, 剩余的空间可能放入其他体积更小的物品, $Greedy (\cal I) \ge \alpha$
- 背包问题的最优解 $OPT (\cal I) $: 整数规划的最优解一定不优于线性规划, 因此 $OPT_{LP} (\cal I) \le OPT_{LP} (\cal I) \le \alpha + \beta$
因此该算法的近似比为:
$$
\frac{OPT(\cal I)}{Greedy(\cal I)}\le \frac{OPT_{LP}(\cal I)}{Greedy(\cal I)} \le \frac{\alpha + \beta}{\alpha} = 1 + \frac{\beta}{\alpha}
$$
然而, $ \beta/ \alpha$ 可能趋于正无穷: 设前 $m$ 个物品的体积和为 $2\epsilon$, 单位价值为 $v_0 $, 后面的物品的体积为 $ K-\epsilon$, 单位价值为 $v_0 /2 $, 此时无法再放入其他物品, $\beta/ \alpha = (K-\epsilon) / 4\epsilon$ , 当 $\epsilon$ 很小时趋于无穷大。
- 这里可以加入一个小判断: 当$\beta > \alpha $时, 算法只取价值 $\beta$ 的这个物体 (在算法开始前保证$v_i \le K$ ), 此时算法的近似比为 2。
动态规划 (PPTAS)
背包问题是动态规划中的基础问题:
$F_j(i)$ 表示: 前 $j$ 个物品中价值和为 $i$ 的物品所需的最小空间。最优解为 $ F_n(1), …, F_n(\sum v)$ 中 $F_n(i) \le K $ 中 $i$ 最大的情况。
$$
OPT = \arg\max {i \vert F_n(i) \le K} \
$$
$$
F_1(0) = 0, F_1(i \le v_1) = s_1 , F_1(i > v_1) = +\infty\
$$
$$
F_j (i) = \min{ F_{j-1}(i), F_{j-1}(i-v_j) + s_j}
$$
第三行分别表示不取第 $j$ 个物品与取第 $j$ 个物品。算法的时间复杂度为 $O(n\sum v_i) \le O(n^2 v_\max)$。
由于时间复杂度与 $v_\max$ 有关, 这是一个伪多项式时间复杂度的算法: 当 $v_\max$ 很大时, 输入的 bit 数 $x = \log v_\max$ , 标准时间复杂度为 $O(n^2 2^x)$。
近似算法
顺着上面动态规划的方法, 我们先介绍一个完全多项式时间的近似算法:
上面方法是伪多项式时间的原因是时间复杂度与 $v_\max$ 有关, 因此我们希望将时间复杂度中的 $v_\max$ 去掉。
另每个物品的价值减小为 $$v_i’ = \lfloor\frac{v_i}{K}\rfloor$$ 用动态规划求解当前的最优解, 时间复杂度为 $$O(\frac{n^2V_{\max}}{K})$$
设当前问题的最优解为$ S’$ , 原问题的最优解 $S^*$ 。首先计算当前问题与原问题的误差:
$$
\begin{align}
\sum_{j\in S’} V_j &\ge\lfloor \sum {j \in S’} \frac{V_j}{K} \rfloor\cdot K \
&= K \cdot\sum{j\in S’} V_j’ \
&\ge K\cdot\sum_{j\in S^*} V_j’\
&\ge \sum_{j \in S^*}(\frac{V_j}{K}-1)\cdot K\
&= \sum_{j\in S*}V_j - K\vert S^*\vert \
&\ge OPT - n K
\end{align}
$$
- 由下界显然成立
- $$v_i’ = \lfloor\frac{v_i}{K}\rfloor$$ 使我们定义的物品新的价值
- 在新的问题中, 最优解为$ S’$ ,而$S^*$ 为可行解, 最优解的值大于等于任意的可行解
- $v_i’ = \lfloor\frac{v_i}{K}\rfloor\ge \frac{v_i}{K}-1 $
- 展开
- $ \vert S^*\vert \le n$
为了使误差 $nK \le \epsilon\cdot OPT$
$$
\begin{align}
&nK \le \epsilon\cdot OPT \
\Leftarrow &K \le \frac{\epsilon\cdot OPT }{n} \
\Leftarrow &K \le \frac{\epsilon\cdot v_\max }{n}\
\end{align}
$$
最后一行: $ OPT \ge v_\max$ (只需取价值最大的物品即可得到$v_\max$ 的解) 因此 $ K \le \frac{\epsilon\cdot v_\max }{n} \le \frac{\epsilon\cdot OPT }{n}$
取 $ K = \frac{\epsilon}{n} v_{\max}$, 此时时间复杂度为 $$O(\frac{n^2v_{\max}}{K}) = O(\frac{n^3}{\epsilon})$$, 是一个完全多项式时间近似算法。
