背包问题

一些概念

介绍背包问题之前，先说明几个概念。

标准时间复杂度：在标准时间复杂度中，输入规模的定义为：保存输入数据所需要的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$, $$ 表示该算法的误差参数 $ = $

多项式时间近似算法 (PTAS (Polynomial time approximation scheme)) : 对于每一个固定的 $\epsilon >0$ ，算法 $\cal A$ 的运行时间以实例 $\cal I$ 的规模的多项式为上界。

然而有多项时间近似算法并不一定就有很好的应用, 因为很多算法都是$1/ $ 的指数时间算法,如 $ O(n^{1/})$ , 当我们希望误差小于 1% 时, 算法复杂度可能高达 $ O(n^{100})$ , 因此提出一个更强的要求:

完全多项式时间近似算法 (FPTAS (Fully polynomial time approximation scheme)): 算法 $\cal A$ 的运行时间以实例 $\cal I$ 的规模和 $1/ $ 的多项式为上界。即算法复杂度为 $ O(n^k / ^ 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 (I) $: 前 $m$ 个物品也会被取到, 剩余的空间可能放入其他体积更小的物品, $Greedy (\cal I) \ge \alpha$
背包问题的最优解 $OPT (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} \]

然而, $ / $ 可能趋于正无穷: 设前 $m$ 个物品的体积和为 $2\epsilon$, 单位价值为 $v_0 $, 后面的物品的体积为 $ K-$, 单位价值为 $v_0 /2 $, 此时无法再放入其他物品, $\beta/ \alpha = (K-\epsilon) / 4\epsilon$ , 当 $\epsilon$ 很小时趋于无穷大。

这里可以加入一个小判断: 当$> $时, 算法只取价值 $\beta$ 的这个物体 (在算法开始前保证$v_i \le K$ ), 此时算法的近似比为 2。

动态规划 (PPTAS)

背包问题是动态规划中的基础问题:

$F_j(i)$ 表示: 前 $j$ 个物品中价值和为 $i$ 的物品所需的最小空间。最优解为 $ F_n(1), …, F_n(v)$ 中 $F_n(i) 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’ = -1 $
展开
$ S^*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 v_$ (只需取价值最大的物品即可得到$v_\max$ 的解) 因此 $ K $

取 $ K = v_{}$, 此时时间复杂度为 \[O(\frac{n^2v_{\max}}{K}) = O(\frac{n^3}{\epsilon})\], 是一个完全多项式时间近似算法。