背包是线性DP中重要且特殊的一类模型，可以分为0/1背包、完全背包、多重背包和分组背包四类。

0/1背包

问题模型

给定 $N$ 个物品，其中第 $i$ 个物品的体积为 $V_i$，价值为 $W_i$。有一个容积为 $M$ 的背包，要求选择一些物品放入背包，使得物品总体积不超过 $M$ 的前提下，物品的总价值和最大。

阶段：用已处理的物品数作为 DP 的阶段，以背包中已经放入的物品的总体积作为附加维度。

$ F[i, j]$ 表示从前 $i$ 个物品中选出了总体积为 $j$ 的物品放入背包，物品的最大价值和。则有状态转移方程：
$$
F[i][j] = max
\left\{
\begin{array}{**lr**}
F[i-1,j], & 不选第i个物品 \\
F[i-1, j-V_i] + W_i \;（if \;j\geq V_i ）& 选第i个物品
\end{array}
\right.
$$
初始值：$F[0, 0] = 0$，其余为负无穷，目标：$ \max \limits_{0 \leq j \leq M}\{F[N][j]\}$。

求解代码

1
2
3
4
5
6
7
8
9
10
11
memset(f, 0xcf, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
  for (int j = 0; j <= m; ++j)
   		f[i][j] = f[i-1][j];
  for (int j = v[i]; j <= m; ++j)
    	f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
}
int ans = 0;
for (int j = 0; j <= m; ++j)
  	ans = max(ans, f[n][j]);

经过状态压缩之后

1
2
3
4
5
6
7
8
9
memset(f, 0xcf, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; ++i) {
  for (int j = m; j >= v[i]; --j)  // 倒叙遍历
    	f[j] = max(f[j], f[j-v[i]] + w[i]);
}
int ans = 0;
for (int j = 0; j <= m; ++j)
  	ans = max(ans, f[j]);

一般问题可能有两类，一类是问最大值，一类是问方案数目。决策转移时，分别使用最大值判断和相加即可。

完全背包

问题模型

给定 $N$ 个物品，其中第 $i$ 个物品的体积为 $V_i$，价值为 $W_i$ ，并且有无数个。有一个容积为 $M$ 的背包，要求选择一些物品放入背包，使得物品总体积不超过 $M$ 的前提下，物品的总价值和最大。

阶段：用已处理的物品数作为DP的阶段，以背包中已经放入的物品的总体积作为附加维度。

$ F[i, j]$ 表示从前 $i$ 种物品中选出了总体积为 $j$ 的物品放入背包，物品的最大价值和。则有状态转移方程：
$$
F[i][j] = max\left\{
\begin{array}{**lr**} F[i-1,j], & 不选第i种物品 \\
F[i, j-V_i] + W_i \;（if \;j\geq V_i ）& 从第i种物品种选择一个
\end{array}
\right.
$$
初始值：$F[0, 0] = 0$，其余为负无穷，目标：$ \max \limits_{0 \leq j \leq M}\{F[N][j]\}$。

求解代码

直接放经过状态压缩之后的代码。

1
2
3
4
5
6
7
8
9
memset(f, 0xcf, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; ++i) {
  for (int j = v[u]; j <= m; ++j)  // 正序遍历
    	f[j] = max(f[j], f[j-v[i]] + w[i]);
}
int ans = 0;
for (int j = 0; j <= m; ++j)
  	ans = max(ans, f[j]);

多重背包

问题模型

给定 $N$ 个物品，其中第 $i$ 个物品的体积为 $V_i$，价值为 $W_i$ ，并且有 $C_i$ 个。有一个容积为 $M$ 的背包，要求选择一些物品放入背包，使得物品总体积不超过 $M$ 的前提下，物品的总价值和最大。

直接拆分法：把第 $i$ 种物品看作独立的 $C_i$ 个物品，从未转化为0/1背包问题，但时间复杂度较高。

二进制拆分法：待补充。

单调队列法：待补充。

例题：Coins

给定 $N$ 种硬币，其中第i种硬币的面值为 $A_i$，共有 $C_i$ 个。从种选出若干硬币，把面值相加，若结果为 $S$，则称“面值 $S$ 能被拼成”。求 1～N 之间能被拼成的面值有多少个。

$1\leq N\leq 100, 1\leq M \leq 10^5, 1 \leq A_i \leq 10^5, 1 \leq C_i \leq 1000$。

以“已考虑过的物品种数”作为 DP 的阶段，在阶段 $i$ 时，$F[j]$ 表示前i种硬币是否能够拼成面值 $j$。“直接拆分法”的求解片段。

1
2
3
4
5
6
7
8
9
10
11
12
bool f[100010];
memset(f, 0, sizeof(f));
f[0] = true;
for (int i = 1; i <= n; ++i) {
  	for (int j = 1; j <= c[i]; j++) {
      	for (int k = m; k >= a[i]; k--)
          f[k] |= f[k-a[i]];
    }
}
int ans = 0;
for (int i = 1; i <= m; ++i)
  	ans += f[i];

上述代码复杂度过高，进行优化。

前i中硬币能够拼成面值 $j$，只有两种可能情况：

  1. 前 $i-1$ 种硬币已经可以拼成面值 $j$。
  2. 使用了第 $i$ 种硬币，在第 $i$ 阶段递归时，发现 $F[j-a[i]]$ 为 true ，从而 $F[j]$ 变为true。但是该种条件下应该满足，$F[j-a[i]]$ 为 true 时，使用的第 $i$ 种硬币应该小于 $C_i$。

假设 $used[j]$ 表示 $F[j]$ 在阶段 $i$ 时为 true 至少需要多少枚第 $i$ 种硬币。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int used[100010];
bool f[100010];
memset(f, 0, sizeof(f));
f[0] = true;
for (int i = 1; i <= n; ++i) {
  	for (int j = 0; j <= m; ++j)
        used[j] = 0;
    for (int j = a[i]; j <= m; ++j) {
      	if (!f[i] && f[j-a[i]] && used[j-a[i]] < c[i]) {
          	f[j] = true;
          	used[j] = used[j-a[i]] + 1;
        }
    }
}
int ans = 0;
for (int i = 1; i <= m; ++i)
  	ans += f[i];

分组背包

问题模型

给定 $N$ 个物品，其中第 $i$ 组有 $C_i$ 个物品。第 $i$ 组的第 $j$ 个组品的体积为 $V_{ij}$，价值为 $W_{ij}$ 。有一个容积为 $M$ 的背包，要求选择一些物品放入背包，使得每组至多选择一个物品并且物品总体积不超过 $M$ 的前提下，物品的总价值和最大。

$ F[i, j]$ 表示从前 $i$ 组物品中选出了总体积为 $j$ 的物品放入背包，物品的最大价值和。则有状态转移方程：
$$
F[i][j] = max
\left\{
\begin{array}{**lr**}
F[i-1,j], & 不选第i组物品 \\
\max \limits_{1\leq k\leq C_i} F[i-1, j-V_{ik}] + W_{ik} \;（if \;j\geq V_{ik} ）& 选第i组的某物品k
\end{array}
\right.
$$

求解代码

经过空间压缩后的求解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
memset(f, 0xcf, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; ++i) {
  	for (int j = m; j >= 0; --j) {
      	for (int k = 1; k <= c[i]; ++k) {
          	if (j >= v[i][k])
              	f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);
        }
    }
}
int ans = 0;
for (int j = 1; j <= m; ++j)
  	ans = max(ans, f[j]);