# 背包问题

## 问题定义

1. 输入是一个有 $n$ 个物品的集合，每个都有一个重量 $w_i$ 和 价格 $b_i$，且有一个背包含重量 $W$ 的限制，求一个最优解，使得总重量不超过 $W$，且总价格最大

2. 基础的可切分背包问题只需选取性价比最高的物品，用贪心算法就可以解决

3. 0-1 背包问题：每个物品只有一个，要么选要么不选
   - 不能通过贪心解决，比如只有两个物品，一个重 $W$，价格 $W$，一个重 $\epsilon$，价格 $2\epsilon$，而按性价比贪心会先选第二个，此时不能再选取第一个，而实际应该只选取第一个
   - 一个近似贪心算法：先按性价比贪心，在不能选取时，查看前面所有物品和不能放进的物品，如果前面总收益更大，则不替换，否则，替换掉前面的物品，可以保证最终结果至少是最优解的一半
     - 证明：前面有 $a_1,\ldots,a_{k-1}$，恰不能放进的是 $a_k$，则有 $b_1+\cdots+b_{k-1}+b_k\geqslant OPT$，因为是按性价比来排的，且最终选取的是前面总和与后者更大的一个，因此最终结果比最优解的一半更强

4. 有些问题不适用于多项式时间的算法，想要解决这些问题，可以考虑近似算法，即找到一个多项式时间的算法，使得其结果与最优解的差距不大；而想要找到一个精确解，需要考虑各种 corner case，从近似解到精确解需要的时间可能远大于达到近似解的时间

## 背包问题的动态规划方法

1. 第一种假设所有的重量 (包括每个物品和背包能承受的总重)都为整数
   - 定义子问题 $V[k,w]$ 为使用前 $k$ 个物品，且背包重量为 $w$ 时的最优解，则有 $$V[k,w]=\begin{cases}V[k-1,w],&w_k>w\\\max(V[k-1,w],V[k-1,w-w_k]+b_k),&else\end{cases}$$
   - 时间复杂度为 $O(nW)$
   - 这个时间复杂度不是多项式时间，因为 $W$ 为一个数，是数值而不是数量，一个数值对应的复杂度输入规模为 $l=\log W$，因此时间复杂度为 $O(n\cdot 2^l)$

> 伪多项式算法：一个问题的复杂度应该是相对于输入规模而定的，比如一个数值的输入规模为其的对数，因此朴素的求是否质数方法为 $O(n^{1/2})=O(2^{l/2}),l=\log n$
> PTAS，Polynomial Time Approximation Scheme，knapsack, TSP (旅行商问题)

2. 第二种假设所有物品的价值为整数
   - 定义子问题 $S[i,p]$ 为前 $i$ 个商品的子集价值和恰好为 $p$ 时所需的最小重量，如果没有这样的子集，则对应取 $\infty$
   - 有如下递推式 $$S[i,p]=\begin{cases}\min(S[i-1,p],S[i-1,p-b_i]+w_i),&b_i\leqslant p\\S[i-1,p],&else\end{cases}$$
   - 其中 $p\leqslant nP,P=\max b_i$
   - 把所有能达到的收益都取出来，其中小于背包重量的那个就是最优解   
   - 时间复杂度为 $O(n^2P)$，同样为伪多项式时间
   - 如何将这个伪多项式时间复杂度转为多项式时间近似算法？可以取归一化 $b_i'=\lfloor \frac{b_i}{P}\cdot\frac{n}{\varepsilon}\rfloor$，这样最大值为 $P'=\frac{n}{\varepsilon}$，总的时间复杂度为 $O(\frac{n^3}{\varepsilon})$ 为多项式时间复杂度，但这个新问题的最优解不是原问题的最优解，可以证明新问题的最优解至少为 $(1-\varepsilon)OPT$，因此可以得到一个多项式时间 $(1-\varepsilon)$-近似算法