背包问题
概述
背包问题是一类经典的动态规划问题。它通常可以抽象出一个容积为\(V\)的背包，\(n\)个物品且每个物品均有其对应的价值\(w\)（\(weight\)）和体积\(c\)（\(cost\)），要求选出若干个物品，使其体积总和不超过\(V\)且价值总和最大。
上述问题即为\(01\)背包问题。\(01\)背包可以拓展出很多变种：
-
多重背包，每个物品的数量可以为复数；
-
完全背包，每个物品的数量不限；
-
分组背包，物品可以分成若干组，每组只能选一个物品；
-
依赖背包，选择某个物品还要选择其依赖的物品。
背包问题作为一类经典的动态规划模型，其可拓展性和难度均较高，如\(CSP2019-PJT3\)就是一个背包问题。
\(01\)背包
\(01\)背包是最基础的背包问题，对于每个物品仅有选和不选两种状态。复杂的背包问题均可以直接或间接转化成\(01\)背包。
设\(dp_{i, j}\)为前\(i\)个物品，体积总和不超过\(j\)时的最大价值总和。对于第i个物品，我们有选与不选两种决策：
-
选，则前\(i – 1\)个物品的体积总和不能超过\(j – c[i]\)，故\(dp_{i, j} = min(dp_{i – 1, j}, dp_{i – 1, j – c_{i}} + w_{i})\)。
-
不选，不进行状态转移。
此算法的时间复杂度为\(O(NV)\)，空间复杂度为\(O(NV)，\)其中\(N\)为物品数，\(V\)为背包的最大容积。
朴素的\(01\)背包解法空间开销太大，考虑进一步优化状态。试去掉第一维，将状态改为\(dp_{j}\)表示体积不超过\(j\)时的最大价值总和。
考虑状态转移时\(dp_{j – c_{i}}\)的更新来源。因为当枚举到第\(i\)个物品时，最大体积为\(j\)时，第\(i\)个物品没有对\(dp_{j – c_{i}}\)进行转移，故而\(dp_{j – c_{i}}\)总是在仅有前\(i – 1\)个物品时的状态，即\(dp_{j – c_{i}}\)等于旧状态的\(dp_{i – 1, j – c_{i}}\)，所以旧状态的第一维可以优化。
如果用一维状态求解，则枚举顺序需要发生变化。我们用两层循环枚举，第一层\(1\) -> \(n\)，枚举物品；第二层\(V\)到\(c_{i}\)，倒序枚举体积。因为正序枚举可能会导致\(dp_{j}\)不等于\(dp_{i – 1,j}\)（具体证明略），所以需要倒序枚举体积。
如果 –脑抽– 无法理解状态优化，还可以使用滚动数组的技巧优化状态。因为状态转移只需要用到\(dp_{i – 1}\)时的状态，所以可以使用优化。此处不赘述原理，只给出具体写法：
for (int i = 1; i <= n; i++)
{
for (int j = c[i]; j <= v; j++)
dp[flag][j] = max(dp[flag][j], dp[!flag][j - c[i]] + w[i]);
flag = !flag;
}
注意，因为最后数组多反转了一次，所以最终答案存在dp[!flag][v]中。
无论是状态删减或者滚动数组，\(01\)背包问题的最终解法时间复杂度均为\(O(NV)\)，空间复杂度优化到了\(O(V)\)。
多重背包
朴素算法
每个物品有其对应的属性：体积\(c\)、价值\(w\)和数量\(k\)。要求选出若干物品，使容积为\(V\)的背包可以装下且价值和最大。
对于这一类问题，我们可以加一重循环枚举物品数量\(k\)，从而将问题转化成一个\(01\)背包问题。同样地，多重背包也可以进行空间的优化。注意到对于每个物品，如果倒序枚举体积，则\(dp_{j -c[i]\times k}\)永远是\(i – 1\)个物品时的状态，同\(01\)背包一样。
时间复杂度\(O(NV\sum_{i = 1}^{n}k_{i})\)
二进制优化
注意到对于一个\(n\)位的二进制数，它可以表示出\(0\) ~ \(2^{n} – 1\)范围内的任意一个数。联想到多重背包的物品个数\(k\)，对于原来的第\(i\)个物品，我们抽象出若干个物品，对于抽象出的第\(j\)个物品，它的价值为\(2^{j} \times w_{i}\)，它的体积为\(2^{j} \times c_{i}\)。
如果第\(i\)个物品的个数\(k_{i}\)不是\(2\)的整次幂，则多抽象出一个价值为\(w_{i} \times (k_{i} – 2^{n} + 1)\)，体积为\(c_{i} \times (k_{i} – 2^{n} + 1)\)的物品，其中\(n\)为最大的\(2^{n} < k_{i}\)的自然数。
这样，通过组合抽象出的若干个物品，我们总能组合出选\(0\) ~ \(k_{i}\)个物品\(i\)时的情况。整个问题就转化成了一个\(01\)背包问题。二进制优化后，多重背包的时间复杂度为\(O( NV\sum_{i = 1}^{n} log _{2}k_{i})\)，是一个极大的优化！
模板
二进制优化
//建出抽象物品
for (int i = 1; i <= n; i++)
{
int k;
for (k = 1; n[i] - (1 << k) + 1; k++)
{
nc[ncnt] = c[i] * (1 << k);
nw[ncnt] = w[i] * (1 << k);
ncnt++;
}
k--;
nc[ncnt] = c[i] * (n[i] - (1 << k) + 1);
nw[ncnt] = w[i] * (n[i] - (1 << k) + 1);
ncnt++;
}
完全背包
给定若干物品，每个物品有其对应的价值\(w\)和体积\(c\)。每个物品的数量无限，换言之，同一个物品可以选无数次。给定一个容积为\(V\)的背包，请选出若干物品，使得它们的体积之和不超过\(V\)且价值总和最大。
完全背包似乎是一个无解的问题。从多重背包的思考角度出发，我们枚举物品的个数\(k\)可以从\(0\)枚举到\(\infty\)，因此，我们不可能求解完全背包问题。
实际上，完全背包问题是有解的。因为背包的容积有限，所以每个物品不能选超过\(\frac{V}{c_{i}}\)次，故而完全背包问题可以转化成多重背包问题求解。这种解法的时间复杂度是\(O(NV\sum_{i = 1}^{n}\frac{V}{c_{i}})\)。
注意到\(dp_{j}\)实际上等于二维状态下（\(dp_{i, j}\)表示前\(i\)个物品体积不超过\(j\)时的最大价值和）的\(max(dp_{i – 1, j – c_{i}}, dp_{i – 1, j – c_{i} \times 2}, dp_{i – 1, j – c_{i} \times 3}, …)\)，而\(dp_{j – c_{i}}\)等于\(max(dp_{i – 1, j – c_{i} \times 2}, dp_{i – 1, j – c_{i} \times 3}, dp_{i – 1, j – c_{i} \times 4}, …)\)。
联想到\(dp_{j}\)实际上可以通过\(dp_{j – c_{i}}\)来转移，即\(dp_{j} = max(dp_{j}, dp_{j – c{i}} + w_{i})\)。具体证明此处不再赘述（因为显然）。
由此完全背包就转化成了与\(01\)背包相似的形式。因为进行状态转移时需要用到已经被更新过的\(dp_{j – c_{i}}\)，所以需要正序枚举体积，与\(01\)背包不同。
参考代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 10005
int n, v;
int w[maxn], c[maxn], dp[maxn];
int main()
{
scanf("%d%d", &v, &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &c[i]);
for (int i = 1; i <= n; i++)
for (int j = c[i]; j <= v; j++)
dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
printf("%d\n", dp[v]);
return 0;
}
分组背包
给定\(n\)个物品，每个物品有其对应的体积\(c\)、价值\(w\)和所属组别。对于同一组的物品，只能在其中挑选一个。现在给出一个体积为\(V\)的背包，要求选出若干物品，使得其体积总和不超过\(V\)且价值总和最大。
实际上，分组背包仍然是一个\(01\)背包问题。设\(dp_{j}\)表示体积不超过\(j\)时的最大价值和，因为当枚举到第\(i\)组第\(k\)个物品时，\(dp_{j – c_{i, k}}\)总是前\(i – 1\)组物品时的状态，所以只需要多加一重循环枚举组内的物品即可。
参考代码如下：
#include <cstdio>
#include <vector>
using namespace std;
#define maxn 1005
int n, v;
int cnt[maxn], dp[maxn];
vector<int> w[maxn], c[maxn];
int main()
{
int x, y, z;
scanf("%d%d", &v, &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d", &x, &y, &z);
c[z].push_back(x);
w[z].push_back(y);
cnt[z]++;
}
for (int i = 1; i <= n; i++)
for (int j = v; j >= 0; j--)
for (int k = 0; k < cnt[i]; k++)
if (j >= c[i][k])
dp[j] = max(dp[j], dp[j - c[i][k]] + w[i][k]);
printf("%d\n", dp[v]);
return 0;
}
依赖背包
依赖背包是一类特殊的背包问题。问题中给出的物品大致可以分成两种：
-
主件，包含有若干个附件。
-
附件，从属于某个主件。将附件加入背包必须将主件也加入背包。
而依赖背包问题又大致可以分成两种类型：
-
附件不再有从属于其的附件。
-
附件可以有“附件的附件”。
对于第一类问题，可以暴力地枚举可以转移的状态。即，枚举附件的选举情况，再加上从属的主件进行转移，于是问题就变成了一个组合问题。
对于第二类问题，正解是树形\(dp\)，此处不再深入（因为我也不会）。
此处附上笔者的\(AC\)代码，仅供参考：
#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 65
#define maxm 32005
int n, v;
int C[maxn], W[maxn], q[maxn];
int c[maxn][3], w[maxn][3], dp[maxm];
int main()
{
scanf("%d%d", &v, &n);
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d", &C[i], &W[i], &q[i]);
W[i] *= C[i];
if (!q[i])
{
c[i][0] = C[i];
w[i][0] = W[i];
}
else
{
int j = (c[q[i]][1] | w[q[i]][1]) ? 2 : 1;
c[q[i]][j] = C[i];
w[q[i]][j] = W[i];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = v; j >= 0; j--)
{
if (!q[i])
{
if (j >= c[i][0])
dp[j] = max(dp[j], dp[j - c[i][0]] + w[i][0]);
if (j >= c[i][0] + c[i][1])
dp[j] = max(dp[j], dp[j - c[i][0] - c[i][1]] + w[i][0] + w[i][1]);
if (j >= c[i][0] + c[i][2])
dp[j] = max(dp[j], dp[j - c[i][0] - c[i][2]] + w[i][0] + w[i][2]);
if (j >= c[i][0] + c[i][1] + c[i][2])
dp[j] = max(dp[j], dp[j - c[i][0] - c[i][1] - c[i][2]] + w[i][0] + w[i][1] + w[i][2]);
}
}
}
printf("%d\n", dp[v]);
return 0;
}
变种问题
输出方案
给定一个\(01\)背包的标准输入，输出选取物品的方案。
设\(dp_{j}\)表示体积不超过\(j\)时的最大价值和，\(g_{i, j}\)表示前\(i\)件物品、体积不超过\(j\)时的方案是否选取了第\(i\)个物品。\(g\)数组在状态转移时更新即可。
从最后一个物品开始查找。如果\(g_{i, v} = true\)，说明第\(i\)个物品在方案中，\(v = v – c_{i}\)，否则，说明第\(i\)个物品不在方案中。
参考代码：
#include <cstdio>
#include <stack>
using namespace std;
#define maxn 1005
int n, v;
int w[maxn], c[maxn], dp[maxn];
bool g[maxn][maxn];
stack<int> s;
int main()
{
scanf("%d%d", &v, &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &c[i], &w[i]);
//dp
for (int i = 1; i <= n; i++)
{
for (int j = v; j >= c[i]; j--)
{
if (dp[j - c[i]] + w[i] > dp[j])
{
dp[j] = dp[j - c[i]] + w[i];
g[i][j] = true;
}
}
}
//输出方案
int tempv = v;
for (int i = n; i >= 1; i--)
{
if (g[i][tempv])
{
s.push(i);
tempv -= c[i];
}
}
while (!s.empty())
{
printf("%d\n", s.top());
s.pop();
}
return 0;
}
方案总数
设\(f_{i, j}\)表示前\(i\)个物品、体积刚好为\(j\)时的方案总数。\(f_{i, j} = f_{i – 1, j} + f_{i – 1, j – c_{i}}\)。
初始化\(f_{0} = 1\)，因为什么都不选也是一种方案。
最优方案总数
设\(f_{i, j}\)为前\(i\)个物品、体积刚好为\(j\)时的最大价值和，\(g_{i, j}\)为前\(i\)个物品，体积刚好为\(j\)时的最优方案总数。
-
\(f_{i, j} = f_{i – 1, j}\)且\(f_{i, j} \neq f_{i – 1, j – c_{i}} + w_{i}\)，说明此时不选第\(i\)个物品会更优，\(g_{i, j} = g_{i – 1, j}\)。
-
\(f_{i, j} \neq f_{i – 1, j}\)且\(f_{i, j} = f_{i – 1, j – c_{i}} + w_{i}\)，说明此时将第\(i\)个物品放入背包会更优，\(g_{i, j} = g_{i – 1, j – c_{i}}\)。
-
\(f_{i, j} = f_{i – 1, j}\)且\(f_{i, j} = f_{i – 1, j – c_{i}} + w_{i}\)，说明此时选不选第\(i\)个物品都可以，\(g_{i, j} = g_{i – 1, j} + g_{i – 1, j – c_{i}}\)。
将每个博主的人数看做物品的体积，也就是 \(1\)，粉丝人数看做价值，选 \(k\) 个人看做背包的体积，直接求解最优方案总数即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 5;
const int maxv = 1e3 + 5;
const int mod = 1e9 + 7;
int t, n, v;
int c[maxn], w[maxn], dp[maxn][maxn], g[maxn][maxn];
int main()
{
scanf("%d", &t);
while (t--)
{
memset(dp, 0, sizeof(dp));
scanf("%d%d", &n, &v);
for (int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
c[i] = 1;
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= v; j++)
if (j >= c[i])
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
else
dp[i][j] = dp[i - 1][j];
for (int i = 0; i <= v; i++)
g[1][i] = 1;
for (int i = 2; i <= n; i++)
{
for (int j = 0; j <= v; j++)
{
if (j >= c[i])
{
if ((dp[i][j] == dp[i - 1][j]) && (dp[i][j] != (dp[i - 1][j - c[i]] + w[i])))
g[i][j] = g[i - 1][j] % mod;
if ((dp[i][j] == (dp[i - 1][j - c[i]] + w[i])) && (dp[i][j] != dp[i - 1][j]))
g[i][j] = g[i - 1][j - c[i]] % mod;
if ((dp[i][j] == (dp[i - 1][j - c[i]] + w[i])) && (dp[i][j] == dp[i - 1][j]))
g[i][j] = (g[i - 1][j] + g[i - 1][j - c[i]]) % mod;
}
else
g[i][j] = g[i - 1][j];
}
}
printf("%d\n", g[n][v]);
}
return 0;
}