最近一直在写动态规划相关的算法题，遇到了很多背包问题的变种问题，解法也很精彩，趁着中秋有空，记录于此。
基本的背包问题
背包问题的定义：
有N种物品，对于第i种物品，其体积是$V_i$，价值是$W_i$，数量是$M_i$。现有容量为C的背包，要求从这N种物品中选择一定数量的物品放入背包，使得背包所装的物品价值总和最大。
根据物品数量的不同，又可以把背包问题分为以下三种类型：
- 每种物品的数量都是1，这时称为01背包问题；
- 每种物品的数量都是无限，这时称为完全背包问题；
- 每种物品的数量都是1个或多个，这时称为多重背包问题。
01背包
最简单的是01背包问题，这里简单定义$f(i,j)$为考虑使用前i种物品和容量为j的背包时，所能获取的最大价值。对于第i种物品有两种策略，一种是取，一种是不取，那么01背包的递推式为：
其中，$f(i - 1, j)$表示不取第i种物品，$f(i - 1, j - V_i) + W_i$表示取第i种物品。此时的代码是一个二重循环，因为递推式中只用到了上一轮的状态，所以可以优化空间复杂度，一维数组就可以求解。代码类似于下面这样：1
2
3
4// 01背包
for (int i = 0; i < N; ++i)
for (int j = C; j >= V[i]; --j)
dp[j] = max(dp[j], dp[j - V[i]] + W[i]);
注意到第二层循环是从后往前的，因为$f(i, j)$需要用到$f(i, j - V_i)$，只有从后往前，才能保证用到的是上一轮的状态，即“没有选取过第i种物品”的状态。
完全背包
完全背包的递推式为：
其中，$f(i-1,j)$代表第i种物品一件都不取的子状态，$f(i, j - V_i) + W_i$代表已经取了第i种物品（多少件不知道）的子状态。代码如下：1
2
3
4// 完全背包
for (int i = 0; i < N; ++i)
for (int j = V[i]; j <= C; ++j)
dp[j] = max(dp[j], dp[j - V[i]] + W[i]);
可以看到，与01背包的区别只是第二层的循环顺序不同而已。
多重背包
基本思想是每件物品可以取0,1,2,…,$M_i$件，此时多重背包的递推式为：
时间复杂度是$O(V\Sigma M_i)$。这个时间复杂度在物品件数较高的情况下是较高的，常见的优化为二进制优化，将多重背包问题转化为01背包问题来求解，此时时间复杂度可以下降到$O(Vlog\Sigma M_i)$。
二进制优化：
将第i种物品分成若干件01背包中的物品，其中每件物品有一个系数，该物品的价值和体积都是原来的价值和体积乘上这个系数。这些系数为$1,2,4,8,…,2^{k-1},M_i - 2^k + 1$，其中k是满足$M_i - 2 ^ k + 1 > 0$的最大整数。
一些变种背包问题
要求背包装满
题目链接在这里。题目大意是有一堆硬币，每个硬币有不同的面值以及数量，给定一个值m，要求1至m中有多少个值可以被这些硬币凑出来。看成背包问题来做，好像是一个多重背包问题，背包的最大容量是m。但这题与普通的背包问题又有点区别，普通的背包问题要求的是“背包里物品的价值最大”，而这题转换成背包问题是“哪些容量的背包可以被装满”。这区别可以用初始化来体现，如果不要求背包装满，那么所有的初始状态都是0；如果要求装满，那么只将$f(0,0)$设为0，其他设置为一个表示不合法的特殊值即可。
上面说到多重背包问题可以用二进制优化的思想，转化为01背包问题求解。但对于这道题，这样的时间复杂度还是太高。当背包问题不要求背包里物品价值最大，而仅仅要求装满背包时，可以有$O(NV)$的解法：用$num_j$表示装满容量为j的背包当前物品最多需要多少个，代码如下：
1 | /* |
物品的重量为负值
题目链接在这里。题目大意是每头牛都有一个智力值$S_i$和幽默值$F_i$，要求选出一些牛，这些牛的智力值总和和幽默值总和最大，并且智力值总和必须大于0，幽默值总和也必须大于0。
这题也可以看成背包问题来做，是01背包问题。把智力值当成物品的重量，幽默值当成物品的价值，并且也属于将背包装满的问题。问题在于，物品的重量存在负值。因为数组的索引最小是0，不能存在负值，所以可以人为加一个偏移值offset（比如100000），初始化时令dp[offset]=0，其余位置都设置为一个不合法的值即可。还有一个问题是，01背包问题递推时，要求从后往前，因为$f(i,j)$需要用到$f(i, j-V_i)$的子状态，但是如果$V_i < 0$，此时$j - V_i > j$，应该从前往后更新！具体AC代码节选如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15int inf = 0x3f3f3f3f, offset = 100000;
for (int i = 0; i <= 200000; ++i) dp[i] = -inf;
dp[offset] = 0;
for (int i = 0; i < n; ++i) {
if (s[i] > 0) {
for (int j = 200000; j >= s[i]; --j)
if (dp[j - s[i]] > -inf)
dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
} else {
for (int j = 0; j - s[i] <= 200000; ++j)
if (dp[j - s[i]] > -inf)
dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
}
}
所以从前往后更新也不一定就是完全背包哦^_^。
对于不同物品具有不同的背包上限
题目链接在这里。题目大意是有各种不同高度和数量的砖块，每种砖块的高度是$h_i$，数量是$c_i$，第i种砖块最高只能用在$a_i$以下高度的地方，要求用这些砖块能达到最大的高度是多少。
可以看到这也是一个多重背包问题，物品的重量和价值相同，都是砖块的高度$h_i$，同时也属于把背包装满的问题。考虑到能用尽可能多的砖块，所以$a_i$小的砖块应该先用，所以首先需要对砖块进行排序。同时对于砖块i，其背包容量的上限是$a_i$。总的背包容量上限是最大的$a_i$。
后记
题目总是千变万化，关键是如何将未知的题目转化为已知的题型来求解，这要求对经典的解法有深入的理解。本文所谈及的背包问题变种还只是冰山一角，还有更多未涉及的话题。“我亦无他，唯手熟尔”，很多解题思想并不是只能用在一个地方，而是很多地方都能运用，只有多多练习，以后遇到新的题型才能有更多想法吧，keep moving!