背包九讲 | guanghechen

01背包
¶

有 $N$ 件物品和一个容量为 $C$ 的背包。
其中，第 $i$ 件物品体积为 $v_{i}$ ^[1]，价值为 $w_{i}$ 。
求选择将哪些物品装入背包可使获得的价值总和最大。

问题简析
¶

因为每件物品只有两种选择：放或不放入背包。且每件物品之间相互独立，即无论第 $i$ 件物品怎么选都不影响第 $j (i < j ⩽ N)$ 件物品的决策 ^[2]。故可以考虑前 $i$ 件物品在背包剩余容量为 $c$ 时的最佳决策，即记 $f (i, c)$ 表示当背包剩余容量为 $c$ ，在前 $i$ 件物品中做选择时可以获得的最大价值，不难得到状态转移方程：

f (i, c) = max {f (i - 1, c), f (i - 1, c - v_{i}) + w_{i}}

即枚举背包的剩余容量，在每个容量下，第 $i$ 件物品有“放”和“不放”两种决策，取所有可行决策中的最大值即为在指定容量下选取前 $i$ 件物品能获得的最大价值。

算法优化
¶

在上述转移方程中，不难发现第一维始终是递增的，因此可以使用滚动数组。进一步的，注意到第二维也是具有单调性的，如果我们从 $c = C$ 枚举到 $c = 0$ ，不难发现，在求 $f (i, c)$ 时， $f (i - 1, c)$ 和 $f (i - 1, c - v_{i})$ 所占据的第二维下标均小于或等于 $c$ 。也就是说如果我们只用一个一维数组 $F (c)$ 表示 $f (i - 1, c)$ ，则在求 $f (i, c)$ 时，此时 $F (c) = f (i - 1, c)$ ， $F (c - v_{i}) = f (i - 1, c - v_{i})$ ，若此时将 $f (i, c)$ 赋值给 $F (c)$ ，则有：

F (x) = {\begin{aligned} f (i - 1, x), & 0 ⩽ x < c \\ f (i, x), & c ⩽ x ⩽ C \end{aligned}

而在求 $f (i, c - 1)$ 时再也不需要用到 ${f (i - 1, x) ∣ c ⩽ x ⩽ C}$ 了。

综上，仅需一个一维数组即可完成状态转移，空间复杂度为 $O (C)$ 。同时，由于第 $i$ 个物品仅当背包剩余容量大于等于 $v_{i}$ 时才能做“放入”的决策，因此我们在枚举 $c$ 时只要枚举到 $v_{i}$ 就够了 ^[3]。

初始化细节
¶

01背包问题存在两个变种，仅需改变初始化方式即可求解：

恰好装满背包时可以获得到的最大价值
将 $F$ 初始化为： $F (c) = {\begin{aligned} (1) & 0, & c = 0 \\ (2) & - \infty, & 0 < c ⩽ C \end{aligned}$ .
这样初始化相当于强制转移只能沿着“剩余容量恰好消耗完”的方向进行，若最后 $F (C)$ 不为 $- \infty$ ，则说明可构造出一条转移路径使得背包容量恰好被消耗完，反之，则说明无解。
无需恰好装满背包时，可以获得的最大价值
将 $F$ 初始化为： $F (c) = 0, 0 ⩽ c ⩽ C$ .
即转移时无需考虑剩余容量是否有多余。

小结
¶

空间复杂度： $O (C)$
时间复杂度： $O (N \times C)$

01背包.cpp | 14 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int MAX_C = 20000 + 10;
int F[MAX_C];

int solution(int N, int C) {
  memset(F, 0, (C + 1) * sizeof(int));

  for (int i = 0, V, W; i < N; ++i) {
    scanf("%d%d", &V, &W);
    for (int c = C; c >= V; --c) {
      F[c] = std::max(F[c], F[c - V] + W);
    }
  }
  return F[C];
}

完全背包
¶

有 $N$ 种物品和一个容量为 $C$ 的背包。
其中，第 $i$ 种物品体积为 $v_{i}$ ^[1]，价值为 $w_{i}$ ，且有无限件。
求选择将哪些物品装入背包可使获得的价值总和最大。

问题简析
¶

将第 $i$ 种物品拆分成 $⌊ \frac{C}{v_{i}} ⌋$ 个，则问题转换成了 01背包问题，物品数量总计 $\sum_{i = 1}^{N} ⌊ \frac{C}{v_{i}} ⌋$ 个。

基于此，存在两个优化：

若两种物品 $i$ 和 $j$ 满足 $v_{i} ⩽ v_{j}$ 且 $w_{i} ⩾ w_{j}$ ，则删除第 $j$ 种物品，仅考虑第 $i$ 种物品。因为如果最优解中选用了物品 $j$ ，那么把它取出来换成物品 $i$ 放进去，得到的结果不会更差；
将第 $i$ 种物品拆分成 ${2^{0}, 2^{1}, 2^{2}, \dots, . . . 2^{k}}$ 个 ^[4]，其中 $2^{k} ⩽ ⌊ \frac{C}{v_{i}} ⌋ < 2^{k + 1}$ ，则无论最优结果种物品 $i$ 选了多少个，都能保证存在这样的组合能选到这个数量（如果理解不了，可以想象成二进制表示法）。复杂度降为 $O (C \times \sum_{i = 1}^{N} \log (⌊ \frac{C}{v_{i}} ⌋))$ .

算法优化
¶

之前的分析中展示了可以通过拆分物品的方式将原问题转换为 01背包问题，其实原题和 01背包问题的差别只是在前 $i - 1$ 种物品中做完选择后，在第 $i$ 种物品中可以进行多次选择。那么什么时候能继续从第 $i$ 种物品种进行选择呢？不难发现只要背包剩余容量大于 $v_{i}$ 就可以继续做此决策。

记 $f (i, c)$ 表示当背包容量为 $c$ ，在前 $i$ 种物品中做选择时可以获得的最大价值，则状态转移方程为：

f (i, c) = max {f (i - 1, c), f (i, c - v_{i}) + w_{i}}

观察上面的转移方程，不难发现前面01背包-算法优化中提到的优化策略仍然适用，不同的是， $c$ 的枚举要从 $0$ 到 $C$ 方向进行。则有（注意观察，这里 $F$ 值和01背包中的不同）：

F (x) = {\begin{aligned} f (i, x), & 0 ⩽ x < c \\ f (i - 1, x), & c ⩽ x ⩽ C \end{aligned}

小结
¶

空间复杂度： $O (C)$
时间复杂度： $O (N \times C)$

完全背包.cpp | 14 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int MAX_C = 20000 + 10;
int F[MAX_C];

int solution(int N, int C) {
  memset(F, 0, (C + 1) * sizeof(int));

  for (int i = 0, V, W; i < N; ++i) {
    scanf("%d%d", &V, &W);
    for (int c = V; c <= C; ++c) {
      F[c] = std::max(F[c], F[c - V] + W);
    }
  }
  return F[C];
}

多重背包
¶

有 $N$ 种物品和一个容量为 $C$ 的背包。
其中，第 $i$ 种物品体积为 $v_{i}$ ^[1]，价值为 $w_{i}$ ，共有 $s_{i}$ 件。
求选择将哪些物品装入背包可使获得的价值总和最大。

问题简析
¶

可以延续完全背包的拆分思路，将第 $i$ 种物品拆分成 ${2^{0}, 2^{1}, 2^{2}, \dots, 2^{k - 1}, s_{i} - (2^{k} - 1)}$ 个，其中 $2^{k} ⩽ s_{i} < 2^{k + 1}$ ，这样拆分得到的组合正好可以表达 $0 \sim s_{i}$ 之间的任意整数^[5]。复杂度降为 $O (C \times \sum_{i = 1}^{N} \log s_{i})$ .

算法优化
¶

记 $f (i, c)$ 表示当背包剩余容量为 $c$ ，从前 $i$ 种物品中做选择时可以获得的最大价值，则状态转移方程为：

f (i, c) = max {f (i - 1, c - m \cdot v_{i}) + m \cdot w_{i} ∣ 0 ⩽ m ⩽ s_{i}}

不妨记 $g = f (i - 1), h = f (i)$ 。在描述算法前，先观察下列转移方程组（其中 $0 ⩽ m ⩽ s_{i}$ ）：

\begin{aligned} h (c) & = max {g (c - m v_{i}) + m w_{i}, \dots, g (c - v_{i}) + w_{i}, g (c)} \\ h (c + v_{i}) & = max {g (c - (m - 1) v_{i}) + m w_{i}, \dots, g (c) + w_{i}, g (c + v_{i})} \\ \dots \\ h (c + t v_{i}) & = max {g (c - (m - t) v_{i}) + m w_{i}, \dots, g (c + (t - 1) v_{i}) + w_{i}, g (c + t v_{i})} \\ h (c + (t + 1) v_{i}) & = max {g (c - (m - t - 1) v_{i}) + m w_{i}, \dots, g (c + t v_{i}) + w_{i}, g (c + (t + 1) v_{i})} \\ \dots \end{aligned}

由上述转移方程组，可以列出 $h (c + n v_{i})$ 所需的 $g$ 元素列表：

\begin{aligned} h (c) & \leftarrow g (c - m v_{i}), \dots, g (c - v_{i}), g (c) \\ h (c + v_{i}) & \leftarrow g (c - (m - 1) v_{i}), \dots, g (c), g (c + v_{i}) \\ \dots \\ h (c + t v_{i}) & \leftarrow g (c - (m - t) v_{i}), \dots, g (c + (t - 1) v_{i}), g (c + t v_{i}) \\ h (c + (t + 1) v_{i}) & \leftarrow g (c - (m - t - 1) v_{i}), \dots, g (c + t v_{i}), g (c + (t + 1) v_{i}) \\ \dots \end{aligned}

可以发现，对于 $h (c + t \cdot v_{i})$ 来说，更新它所需要的 $g$ 数列元素中除了首项（ $g (c - (m - t) v_{i})$ ）外，其它元素构成了 $h (c + (t + 1) \cdot v_{i})$ 所需的 $g$ 数列元素的前缀子串。更一般地，记

\begin{aligned} G (x) & = {g (x + m v_{i}) | 0 ⩽ m ⩽ ⌊ \frac{C - x}{v_{i}} ⌋}, 0 ⩽ x < v_{i} \\ H (x) & = {h (x + m v_{i}) | 0 ⩽ m ⩽ ⌊ \frac{C - x}{v_{i}} ⌋}, 0 ⩽ x < v_{i} \end{aligned}

则在求 $H (x)$ 中任意项时，仅需要用到 $G (x)$ 的子串元素，这启发我们可以对 $g$ 进行分组。进一步观察，对比 $h (c)$ 和 $h (c + v_{i})$ 所共同需要的 $g$ 元素项中，后者每一项都加上了一个相同的 $w_{i}$ 值，即 $h (c)$ 和 $h (c + v_{i})$ 所需的 $g$ 元素列表中，每项之间的值大小关系始终保持不变，于是问题可以转换为对数列 $G (x)$ 查询固定长度的区间内的最大值，这是一个经典的滑动窗口问题，利用单调栈可以在均摊 $O (1)$ 的复杂度完成查询。

小结
¶

二进制优化

空间复杂度： $O (C)$
时间复杂度： $O (C \times \sum_{i = 1}^{N} \log s_{i})$

多重背包-01.cpp | 21 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int MAX_C = 20000 + 10;
int F[MAX_C];

int solution(int N, int C) {
  memset(F, 0, (C + 1) * sizeof(int));

  for (int i = 0, V, W, M; i < N; ++i) {
    scanf("%d%d%d", &V, &W, &M);
    for (int k = 1; k <= M; k <<= 1) {
      int m = (k << 1) <= M ? k : M - k + 1;
      int V2 = m * V;
      if (V2 > C) break;

      int W2 = m * W;
      for (int c = C; c >= V2; --c) {
        F[c] = std::max(F[c], F[c - V2] + W2);
      }
    }
  }
  return F[C];
}

单调栈优化

空间复杂度： $O (C)$
时间复杂度： $O (N \times C)$

多重背包-02.cpp | 36 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int MAX_C = 20000 + 10;
int g[MAX_C], h[MAX_C];
int ms[MAX_C];   // 单调栈

int solution(int N, int C) {
  memset(g, 0, sizeof(int) * (C + 1));

  for (int i = 0, V, W, M, ss, tt; i < N; ++i) {
    scanf("%d%d%d", &V, &W, &M);

    std::swap(g, h);
    for (int x = 0; x < V; ++x) {
      // 初始化单调栈
      ss = 0;
      tt = 1;
      ms[0] = 0;
      h[x] = g[x];

      for (int c = x + V, k = 1; c <= C; c += V, k += 1) {
        // 窗口长度最大为 M
        if (k - ms[ss] > M) ss += 1;

        // 单调栈中，栈底元素的值最大
        h[c] = std::max(g[c], g[x + ms[ss] * V] + (k - ms[ss]) * W);

        // 压栈
        for (; ss < tt; --tt) {
          int top = ms[tt - 1];
          if (g[x + top * V] + (k - top) * W > g[c]) break;
        }
        ms[tt++] = k;
      }
    }
  }
  return h[C];
}

混合背包
¶

有 $N$ 种物品和一个容量为 $C$ 的背包。
其中，第 $i$ 种物品体积为 $v_{i}$ ^[1]，价值为 $w_{i}$ 。
每种物品的件数可能为 1 件（[01背包][solution-01背包），无限件（完全背包）及有限件（多重背包）。
求选择将哪些物品装入背包可使获得的价值总和最大。

问题简析
¶

01背包问题可以看做物品件数为 $1$ 的多重背包问题；
类似地，完全背包问题可以看做物品件数为 $⌊ \frac{C}{v_{i}} ⌋$ （再多也装不下了）的多重背包问题；

故而，问题规约成多重背包问题。

小结
¶

01背包问题、完全背包问题均可看做多重背包问题的特例，因此混合背包问题也可以规约成多重背包问题。直接套用多重背包问题的解法即可得到复杂度为 $O (C \times V)$ 的算法。

二进制优化
空间复杂度： $O (C)$
时间复杂度： $O (C \times \sum_{i = 1}^{N} \log s_{i})$
单调栈优化
空间复杂度： $O (C)$
时间复杂度： $O (N \times C)$

二维费用的背包
¶

有 $N$ 件物品和一个容量为 $C$ 、最大承重为 $L$ 的背包。
其中，第 $i$ 件物品体积为 $v_{i}$ ^[1]，重量为 $m_{i}$ ，价值为 $w_{i}$ 。
求选择将哪些物品装入背包可使获得的价值总和最大。

问题简析
¶

虽然增加了重量一维，但是转移的状态并没有发生改变，可以完全套用 01背包的思路，只是在判断是否可以转移时要多检查一次重量是否满足条件。

记 $f (i, c, l)$ 表示当背包剩余容量为 $c$ 、剩余最大承重为 $l$ 时，在前 $i$ 件物品中做选择时可以获得的最大价值，不难得到状态转移方程：

f (i, c, l) = max {f (i - 1, c, l), f (i - 1, c - v_{i}, l - m_{i}) + w_{i}}

即枚举背包的剩余容量和剩余承重值，此时第 $i$ 件物品有“放”和“不放”两种决策，取所有可行决策中的最大值即为在指定容量和最大承重下选取前 $i$ 件物品能获得的最大价值。

算法优化
¶

类似01背包中提到的空间优化，二维费用的背包问题也可以省略掉物品数这一维：

用一个二维数组 $F (c, l)$ 表示 $f (i - 1, c, l)$ ，则在求 $f (i, c, l)$ 时，此时 $F (c, l) = f (i - 1, l)$ ， $F (c - v_{i}, l - m_{i}) = f (i - 1, c - v_{i}, l - m_{i})$ ，若此时将 $f (i, c, l)$ 赋值给 $F (c, l)$ ，则有：
$F (x, y) = {\begin{aligned} f (i - 1, x, y), & 0 ⩽ x < c, 或 0 ⩽ y < l \\ f (i, x, y), & c ⩽ x ⩽ C 且 l ⩽ y ⩽ L \end{aligned}$

小结
¶

空间复杂度： $O (C \times L)$
时间复杂度： $O (N \times C \times L)$

二维费用的背包问题.cpp | 17 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int MAX_C = 100 + 10;
const int MAX_M = 100 + 10;
int F[MAX_C][MAX_M];

int solution(int N, int C, int T) {
  memset(F, 0, sizeof(F));

  for (int i = 0, V, W, M; i < N; ++i) {
    scanf("%d%d%d", &V, &M, &W);
    for (int c = C; c >= V; --c) {
      for (int m = T; m >= M; --m) {
        F[c][m] = std::max(F[c][m], F[c - V][m - M] + W);
      }
    }
  }
  return F[C][T];
}

分组背包
¶

有 $N$ 件物品和一个容量为 $C$ 的背包。
其中第 $i$ 件物品体积为 $v_{i}$ ^[1]，价值为 $w_{j}$ 。
所有物品被划分成 $K$ 组，其中第 $k$ 组物品中有 $K_{k}$ 件物品；组内的物品相互冲突，即每组中最多选一件物品。
求选择将哪些物品装入背包可使获得的价值总和最大。

问题简析
¶

类似01背包问题，只不过在01背包中考虑的是“要不要取第 $i$ 件物品”，而在分组背包中考虑的是“要不要取第 $i$ 组物品，要的话该取哪一件”；基于此不难想到，只要在内层循环中依次考虑第 $i$ 组物品内的所有物品的选取与否^[6]就可以等效为01背包问题了。

小结
¶

空间复杂度： $O (N \times C)$
时间复杂度： $O (N \times C)$

分组背包问题.cpp | 20 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MAX_C = 10000 + 10;
const int MAX_N = 100 + 10;
int F[MAX_C], V[MAX_N], W[MAX_N];

int solution(int N, int C) {
  memset(F, 0, sizeof(F));

  for (int i = 0, K; i < N; ++i) {
    scanf("%d", &K);
    for (int k = 0; k < K; ++k) scanf("%d%d", V + k, W + k);

    for (int c = C; c >= 0; --c) {
      int& ans = F[c];
      for (int k = 0; k < K; ++k) {
        if (c >= V[k]) ans = std::max(ans, F[c - V[k]] + W[k]);
      }
    }
  }
  return F[C];
}

有依赖的背包
¶

有 $N$ 个物品和一个容量为 $C$ 的背包。
第 $i$ 件物品体积为 $v_{i}$ ^[1]，价值为 $w_{i}$ 。
物品之间具有依赖关系，比如 $x$ 依赖于 $y$ ，则在选择 $x$ 时必须同时选取 $y$ 。
求选择将哪些物品装入背包可使获得的价值总和最大。

简化版的问题
¶

简单起见，不妨假设所有的物品的依赖关系构成一棵树，即除根节点外的所有物品恰好依赖一个物品，且不存在循环依赖。如下图所示， $B$ 和 $C$ 依赖 $A$ ， $D$ 和 $E$ 依赖于 $B$ .

不难发现，如果要选取树上的某个节点，则其所有祖先节点都需要选取，但如果我们选取了两个节点，其公共祖先只要选取一次就可以了。反过来思考，如果我们决定要选取某个节点，则其所有的子节点都可选或可不选，此时考虑子节点的选取情况是一个 01背包问题。类似地，递归地考虑决定选取某个子节点时其子节点列表的选取情况。于是问题变成了逐层跑01背包进行状态转移的树形DP。

不妨记 $f (i, v)$ 表示选择了节点 $i$ 及其若干子孙节点（所有选择的子孙节点都满足在以 $i$ 为根节点的子树中的依赖关系）且消耗 $v$ 容量时可以获得到的最大价值^[7]，则初始状态为^[8]：

f (i, c) = {\begin{aligned} w_{i}, & c = v_{i} \\ 0, & c \neq v_{i} \end{aligned}

转移方程为：

f (i, c) = max {f (i, c - k) + f (s, k) | s \in children of i, 0 ⩽ k ⩽ c}

之后沿着树递归进行状态转移就好了。

较一般的问题
¶

依然假设依赖关系中不存在环，则所有节点根据依赖关系连边构成的图是一个“森林”，问题变成了以“树”为分组的分组背包问题。而“森林”中的每棵树都可以应用简化版的问题中提到的算法来求解。

因为分组背包的时间也复杂度为 $O (N \times C)$ ，所以最后合并森林时的复杂度和合并树中子节点的复杂度相同，故总时间复杂度仍为 $O (N \times C^{2})$ .

小结
¶

简化版的问题

空间复杂度： $O (N \times C)$
时间复杂度： $O (N \times C^{2})$

有依赖的背包问题.cpp | 41 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int MAX_N = 100 + 10;
const int MAX_C = 1000 + 10;
int N, C, f[MAX_N][MAX_C], V[MAX_N];
std::vector<int> G[MAX_N];

void dfs(int u) {
  int* h = f[u];
  for (int v : G[u]) {
    // 计算子节点的泛化背包值
    dfs(v);

    int* g = f[v];
    for (int c = C; c >= V[u]; --c) {
      int& ans = h[c];
      for (int k = c - V[u]; k >= 0; --k) {
        ans = std::max(ans, h[c - k] + g[k]);
      }
    }
  }
}

int solution() {
  int root = -1;

  scanf("%d%d", &N, &C);
  for (int i = 0, v, w, p; i < N; ++i) {
    scanf("%d%d%d", &v, &w, &p);

    V[i] = v;
    memset(f[i], 0, sizeof(int) * (C + 1));
    if (v <= C) f[i][v] = w;

    if (p == -1)
      root = i;
    else
      G[p - 1].push_back(i);
  }
  dfs(root);

  return f[root][C];
}

较一般的问题
空间复杂度： $O (N \times C)$
时间复杂度： $O (N \times C^{2})$

泛化物品
¶

定义
¶

泛化物品指的是某类虚拟的物品，它的价值随着被分配给它的费用而变化，本质上是对于一类特殊数列或函数的概括和解释，引入它的本质是为了描述在求解背包问题是得到的中间数列，如在有依赖的背包中所所提到的，通过计算子节点而合成的描述父节点关于容量和费用的一个数列。比如，一件费用为 $v$ 价值为 $w$ 的物品：

如果它是01背包问题中的物品，那么用于描述它的费用函数为：
$h (c) = {\begin{aligned} w, & c = v \\ 0, & c \neq v \end{aligned}$
如果它是完全背包中的物品，那么用于描述它的费用函数为：
$h (c) = {\begin{aligned} \frac{c}{v} \cdot w, & v ∣ c \\ 0, & v ∤ c \end{aligned}$
如果它是多重背包中的物品，不妨记它有 $s$ 件，那么用于描述它的费用函数为：
$h (c) = {\begin{aligned} \frac{c}{v} \cdot w, & v ∣ c and \frac{c}{v} ⩽ s \\ 0, & v ∤ c or \frac{c}{v} > s \end{aligned}$

泛化物品的和
¶

对于给定的费用 $C$ ，如何求从两个泛化物品中进行选取可以获得的最大价值呢？^[9]

其实只需要枚举分配给其中一件物品的费用额度，将剩余的费用额度分配给另一件物品，对它们在给定额度下能获得的最大值求和，则答案是所有枚举情况下能获得价值的最大值。不妨记两件物品的费用函数为 $h_{1}$ 和 $h_{2}$ ，则：

f (C) = max {h_{1} (c) + h_{2} (C - c) | 0 ⩽ c ⩽ C}

得到的仍然是一个泛化物品的费用函数，即泛化物品的和仍为一个泛化物品，这或许可以更直观地解释有依赖的背包中合并相邻兄弟节点或两棵树的含义。

背包问题变种
¶

打印方案
¶

以总体积不超过背包容量的01背包问题为例。先考虑第 $N$ 个物品是否能够出现在答案中，若是，则必然有 $f (N, C) = f (N - 1, C - v_{i}) + w_{i}$ ，则问题变成了打印前 $N - 1$ 个物品中放入容量为 $C - v_{i}$ 的背包中的方案问题了。

几个细节：

在检查是否可以选取物品 $i$ 时需要判断背包剩余容量是否能装下它；
因为检查时都是通过 $f (i - 1)$ 进行判断的，因此对 $i = 0$ 要做特判；

01背包-方案打印.cpp | 35 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int MAX_C = 1000 + 10;
const int MAX_N = 1000 + 10;
int F[MAX_N][MAX_C], V[MAX_N], W[MAX_N];
std::vector<int> ans;

void solution(int N, int C) {
  ans.clear();
  if (N <= 0) return;

  for (int i = 0; i < N; ++i) scanf("%d%d", V + i, W + i);

  // Initialize.
  memset(F[0], 0, std::min(C + 1, V[0]) * sizeof(int));
  for (int c = V[0], w = W[0]; c <= C; ++c) F[0][c] = w;

  for (int i = 1; i < N; ++i) {
    const int v = V[i];
    const int w = W[i];

    memcpy(F[i], F[i - 1], std::min(C + 1, v) * sizeof(int));
    for (int c = v; c <= C; ++c) {
      F[i][c] = std::max(F[i - 1][c], F[i - 1][c - v] + w);
    }
  }

  int c = C;
  for (int i = N - 1, w = F[i][C]; i > 0; --i) {
    if (c >= V[i] && F[i - 1][c - V[i]] + W[i] == w) {
      ans.push_back(i + 1);
      c -= V[i];
      w -= W[i];
    }
  }
  if (c >= V[0]) ans.push_back(1);
}

最小字典序方案
¶

此处的“最小字典序”指的是可行方案中的物品编号排成的序列的字典序最小。

仍以总体积不超过背包容量的01背包问题为例，在前面的分析中，我们其实得到了“最大字典序”方案，因为每次都是优先考虑编号大的物品，所以即便存在多个方案，我们也是优先取的大编号物品，因而得到的字典序是最大的。

不难想到，只要将原数组reverse一下再跑前文所述的打印方案的算法，则得到的就是“最小字典序方案”了。

01背包-最小字典序方案.cpp | 35 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int MAX_C = 1000 + 10;
const int MAX_N = 1000 + 10;
int F[MAX_N][MAX_C], V[MAX_N], W[MAX_N];
std::vector<int> ans;

void solution(int N, int C) {
  ans.clear();
  if (N <= 0) return;

  for (int i = N - 1; i >= 0; --i) scanf("%d%d", V + i, W + i);

  // Initialize.
  memset(F[0], 0, std::min(C + 1, V[0]) * sizeof(int));
  for (int c = V[0], w = W[0]; c <= C; ++c) F[0][c] = w;

  for (int i = 1; i < N; ++i) {
    const int v = V[i];
    const int w = W[i];

    memcpy(F[i], F[i - 1], std::min(C + 1, v) * sizeof(int));
    for (int c = v; c <= C; ++c) {
      F[i][c] = std::max(F[i - 1][c], F[i - 1][c - v] + w);
    }
  }

  int c = C;
  for (int i = N - 1, w = F[i][C]; i > 0; --i) {
    if (c >= V[i] && F[i - 1][c - V[i]] + W[i] == w) {
      ans.push_back(N - i);
      c -= V[i];
      w -= W[i];
    }
  }
  if (c >= V[0]) ans.push_back(N);
}

方案总数
¶

仍以总体积不超过背包容量的01背包问题为例，记 $f (i, c)$ 表示当背包剩余容量为 $c$ 时，在前 $i$ 件物品中做选择的方案总数；因为是否选取第 $i$ 件物品和前 $i - 1$ 个物品无关，所以简单枚举第 $i$ 件物品的选取情况，然后进行求和即可。不难得到转移方程：

f (i, c) = f (i - 1, c) + f (i - 1, c - v)

几个细节：

初始化：可能最优方案中一个物品也装不下，所以初始化时要将所有的 $f (0, c)$ 设置为 $1$ ，因为什么都不装也是一个方案；
仍可以利用01背包问题中提到的滚动数组来优化空间，方法类似；

01背包-方案总数.cpp | 15 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int MAX_C = 20000 + 10;
int F[MAX_C];

int solution(int N, int C) {
  // Initialize.
  for (int c = 0; c <= C; ++c) F[c] = 1;

  for (int i = 0, V; i < N; ++i) {
    scanf("%d", &V);
    for (int c = C; c >= V; --c) {
      F[c] = F[c] + F[c - V];
    }
  }
  return F[C];
}

最优方案的总数
¶

此处的“最优方案”指物品总体积不超过背包容量且总价值最大的方案。

仍以总体积不超过背包容量的01背包问题为例，记

$f (i, c)$ 表示当背包剩余容量为 $c$ 时，在前 $i$ 件物品中做选择时可以获得的最大价值；
$g (i, c)$ 表示当背包剩余容量为 $c$ 时，从前 $i$ 件物品中进行选择可以获得最大价值的方案数；

则在转移 $f$ 时，顺便统计 $g$ 就可以了：

若 $f (i - 1, c) < f (i - 1, c - V_{i}) + W_{i}$ ，说明找到了一个新方案，其在容量为 $c$ 的背包中能获得的价值比之前所有的方案都要大，因此新的方案数为 $g (i - 1, c - V_{i})$ ；
若 $f (i - 1, c) = f (i - 1, c - V_{i}) + W_{i}$ ，说明找到了一个新方案，其在容量为 $c$ 的背包中能获得的价值和之前的方案一样大，因此新的方案数为 $g (i - 1, c) + g (i - 1, c - V_{i})$
若 $f (i - 1, c) > f (i - 1, c - V_{i})$ ，说明未找到新方案，所以方案数仍为 $g (i - 1, c)$

几个细节：

初始化：可能最优方案中一个物品也装不下，所以初始化时要将所有的 $g (0, c)$ 设置为 $1$ ，因为什么都不装也是一个方案；
仍可以利用01背包问题中提到的滚动数组来优化空间，只不过在转移 $f$ 的状态前，要先做记录，因为需要比较 $f (i - 1, c)$ 和 $f (i - 1, c - V_{i}) + W_{i}$ 的值；

01背包-最优方案数.cpp | 25 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int MAX_C = 20000 + 10;
const int MOD = 1e9 + 7;
int F[MAX_C], G[MAX_C];

int solution(int N, int C) {
  // Initialize.
  for (int c = 0; c <= C; ++c) {
    F[c] = 0;
    G[c] = 1;
  }

  for (int i = 0, V, W; i < N; ++i) {
    scanf("%d%d", &V, &W);
    for (int c = C; c >= V; --c) {
      int total = F[c - V] + W;
      if (F[c] < total) {
        F[c] = total;
        G[c] = G[c - V];
      } else if (F[c] == total) {
        G[c] = (G[c] + G[c - V]) % MOD;
      }
    }
  }
  return G[C];
}

求第 $K$ 优解
¶

待补充。

题目练习

Problem	Category	Solution
01背包问题	01背包	01背包
完全背包问题	完全背包	完全背包
多重背包问题 II	多重背包二进制优化	多重背包
多重背包问题 III	多重背包单调栈优化	多重背包
混合背包	混合背包	混合背包
二维费用的背包	二维费用的背包	二维费用的背包
分组背包	分组背包	分组背包
有依赖的背包	有依赖的背包	有依赖的背包
背包问题求方案数	最优解方案数	最优方案的总数
背包问题求具体方案	背包问题打印方案	最小字典序方案

背包问题九讲 -- 崔添翼

01背包¶

问题简析¶

算法优化¶

初始化细节¶

小结¶

完全背包¶

问题简析¶

算法优化¶

小结¶

多重背包¶

问题简析¶

算法优化¶

小结¶

混合背包¶

问题简析¶

小结¶

二维费用的背包¶

问题简析¶

算法优化¶

小结¶

分组背包¶

问题简析¶

小结¶

有依赖的背包¶

简化版的问题¶

较一般的问题¶

小结¶

泛化物品¶

定义¶

泛化物品的和¶

背包问题变种¶

打印方案¶

最小字典序方案¶

方案总数¶

最优方案的总数¶

求第 K 优解¶

Related¶

01背包
¶

问题简析
¶

算法优化
¶

初始化细节
¶

小结
¶

完全背包
¶

问题简析
¶

算法优化
¶

小结
¶

多重背包
¶

问题简析
¶

算法优化
¶

小结
¶

混合背包
¶

问题简析
¶

小结
¶

二维费用的背包
¶

问题简析
¶

算法优化
¶

小结
¶

分组背包
¶

问题简析
¶

小结
¶

有依赖的背包
¶

简化版的问题
¶

较一般的问题
¶

小结
¶

泛化物品
¶

定义
¶

泛化物品的和
¶

背包问题变种
¶

打印方案
¶

最小字典序方案
¶

方案总数
¶

最优方案的总数
¶

求第 $K$ 优解
¶

Related
¶