背包问题总结
背包问题是动态规划思想和方法的经典应用问题，本文将从0-1背包，完全背包和混合背包三个角度来分析简单背包问题的求解方法。
背包问题
背包问题本质上是规划型问题，问题的核心在于在满足约束条件下，找到一种选择方案，使得目标值达到最优。通过动态规划的方法，可以将此类问题限制在多项式复杂度的时间内求解。
0-1背包
0-1背包问题的描述
有 $N$ 件物品和一个总容量为 $V$ 的背包，第 $i$ 件物品的费用是 $c[i]$，价值是 $w[i]$。求解将哪些物品装入背包可以使得装入的物品的价值总和最大。
0-1背包问题的动态转移
动态转移方程：
\[f[i][v] = max\{f[i-1][v], f[i-1][v-c[i]]+w[i]\}\]解释；对于每一个状态，在决策是否装入第i件时，选取装入与不装入该件物品的价值和的最大值。如果放入第i件物品，那么前 $i$ 件物品最多只能
占用 $v-c[i]$ 的体积，则价值和为 $f[i-1][w-c[i]]$ ，如果不装入第 $i$ 件物品，那么价值和仍为前 $i-1$ 件物品的价值和。
时间和空间复杂度分析
该算法时间复杂度为 $O(V \times N)$，如果只需要求解价值总和的最大值，由于只需要根据价值进行DP，空间复杂度可以优化到 $O(N)$。
代码表述如下：
for(int i = 1; i <= n; ++i) {
for(int j = v; j >= c[i]; j--) {
f[j] = max(f[j], (f[j-c[i]] + w[i]));
/** 不优化空间的写法
* f[i][j] = max(f[i-1][j], (f[i-1][j-c[i]] + w[i]));
*/
}
}
回溯法推导0-1背包问题的最优方案
可以通过回溯的方法求解到底放入了那些背包，在这个求解过程中，不能进行空间的优化，因此，空间占用为 $O(V \times N)$。具体代码表述如下：
/**
* sum 值为之前DP求出的最大价值。
* used 数组用来标记每件物品是否装入。
* 如果第 i 件物品装入了，则 used[i] = true；
* 否则，used[i] = false。
*/
bool used[n] = {false};
for(i = n; i >= 0; --i) {
if(f[i][sum] > f[i-1][sum]) {
used[i] = true;
sum -= w[i];
}
}
另一种获取方案的方法
可以使用一个二维数组flag在更新f时对更新的trace进行记录，然后回溯，便可以得到方案：
int flag[n+1][v+1] = 0;
for(int i = 1; i <= n; ++i) {
for(int j = v; j >= c[i]; j--) {
if(f[j] < f[j-c[i]]+w[i]) {
f[j] = f[j-c[i]] + w[i]);
flag[i][j] = 1;
}
}
}
/**
* 顺序输出物品编号
*/
void output() {
int i = N, j = V;
while(i) {
if(flag[i][j] == 1) {
cout << i << " ";
j -= w[i];
}
i--;
}
cout << endl;
}
/**
* 逆序输出物品编号
*/
void output_reverse() {
if(i == 0 || j == 0) {
return;
}
if(flag[i][j] == 1) {
output_reverse(i-1, j-w[i]);
cout << i << " ";
}
}
完全背包
完全背包问题的描述
有 $N$ 种物品和一个容量为 $V$ 的背包，每种物品有无限件可用。第 $i$ 件物品的费用为 $c[i]$，价值是 $w[i]$。求解将哪些物品装入背包可以使得装入的物品的 价值总和最大，并且物品总费用不能超过背包容量。
完全背包问题的状态转移
显然，完全背包问题可以转换为0-1背包问题，通过总体积来限制背包个数即可。不难得出以下的状态转移方程：
\[f[i][v] = max\{f[i-1][v-k \times c[i]] + k \times w[i]\}\]其中，
\[0 \leq k \times c[i] \leq v\]分析得知，此状态转移求解每个状态的时间已经不是常数了。分析完全背包问题的特点，可以作出优化。分析思路：如果两件物品 $i,j$ 满足 $c[i] <= c[j]$ 且 $w[i] >= w[j]$, 则将物品 $j$ 去掉，不用考虑。优化的正确性在于任何情况下都可以用物美价廉的 $i$ 替换 $j$，至少不会比替换前的方案更差。但此优化在最坏情形下并不能改善问题 的复杂度规模，因为在最坏情况下任何一件物品都不能忽略。
考虑到每种物品都有无限件可以选，因此，在选择第 $i$ 件物品时，只要根据一个绝无已经选入第i种物品的子结果 $f[i-1][v-[i]]$ 即可。在具体实现上，只要改变 $V$ 的 递推顺序就行。
代码表述如下：
for(int i = 1; i <= n; ++i) {
for(int j = c[i]; j <= v; ++j) {
f[j] = max(f[j], f[j-c[i]]+w[i]);
}
}
算法复杂度分析
优化后的时间复杂度为 $O(N \times V)$，空间复杂度为 $O(V)$。
混合背包
混合背包问题的描述
有 $N$ 种物品和一个容量为 $V$ 的背包，第 $i$ 种物品最多有 $n[i]$ 件可用，每件费用为 $c[i]$，价值为 $w[i]$。求解选择方案使得物品价值总和最大，且总重 量不超过背包容量，每件物品的数量也不超过其限制。
混合背包的朴素求解
同混合背包类似，完全背包问题也可以建模为0-1背包模型，但无法在常数时间内求解每个状态，其时间复杂度会达到 $O(n^3)$。
混合背包的二进制拆分求解
二进制拆分实际上是对朴素求解算法的优化。通过二进制拆分可以减少状态数。其原理基于每一个正整数都可以写成数个 $2$ 的自然数次幂之和，并且，每两个幂的次数都 不相同。此优化方案可以将时间复杂度优化到 $O(n^2 \log{n})$。
代码描述如下：
for(int i = 1; i <= n; ++i) {
int s[mi][2], k = 1, t = 0;
while(true) {
if(m[i] <= k) {
s[t][0] = m[i] * c[i], s[t++][1] = m[i] * w[i];
break;
}
else {
s[t][0] = k * c[i], s[t++][1] = k * w[i];
}
m[i] = m[i] - k;
k = k * 2;
}
while(t--) {
for(j = v; j >= s[t][0]; j--) {
f[j] = max(f[j], (f[j-s[t][0]] + s[t][1]));
}
}
}
混合背包的单调队列优化
该算法的思想是根据当前体积模当前物品体积的余数进行分组，每一组的状态都可以有前面的任意一组转换而来。问题可以转化为固定长度区间求最值问题。采用单调队列， 可以将时间复杂度优化到 $O(N \times V)$。
代码表述如下：
/**
* a, b 均为辅助队列，其中，b 是一个单调队列。
*/
for(int i = 1; i <= n; ++i) {
// 优化最多可用的物品件数
if(!n[i] || v/c[i] < n[i]) {
n[i] = v / c[i];
}
for(int d = 0; d < c[i]; ++d) {
int l = 1, r = 0; // 初始化队列参数，清空队列。
for(int j = 0; j <= (v-d)/c[i]; ++j) {
// j 对应的体积为 j*c[i]+d。
int x = j, y = f[j*c[i]+d] - j*w[i]; // 退化
// 插入队列
while(l <= r && b[r] <= y) {
r--;
}
a[++r] = x;
b[r] = y;
// 如果队首元素已经失效，删除失效点。
if(a[l] < j - n[i]) {
l++;
}
// 取得队头，进行更新。
f[j*c[i]+d] = b[l] + j*w[i];
}
}
}
NPC问题
背包问题是一类组合优化的NPC问题。NPC问题指的是：
- 问题W是NP问题；
- 任何一个其他的NP问题都可以在多项式时间内转换为问题W。
通过动态规划，可以在 $O(N*W)$ 的时间复杂度内求解背包问题。但是，$n$ 的确是输入规模的一部分，输入了$n$个重量与价值，但是 $w$ 并不是输入规模， 对于一个数 $W$ ，需要$m=\log{w}$ 的位数来表示。因此，$m$ 才是输入规模的一部分。所以 $O(n \times w) = O(n \times 2^m)$，所以是NPC问题。