背包问题

推公式的瘾犯了，才有了这篇题解

01 背包

问题简述

给你 $N \in \mathbb{N}$ 个物品，其中第 $i$ 个物品具有体积 $v_i \in \mathbb{N}$ 和价值 $w_i \in \mathbb{N}$，和一个容量为 $V \in \mathbb{N}$ 的背包。现在从 $N$ 个物品中选出一些物品，要求在能放入背包的前提下（即选出的物品的体积总和小于等于背包容量）使得选出物品的价值总和最大。

符号约定

首先我们用 $\text{concat}$ 函数表示两个序列 $(a_n)$ 和 $(b_m)$ 的拼接：

$$\large \text{concat} : \mathbb{N}^a \times \mathbb{N}^b \rightarrow \mathbb{N}^{a+b} \quad \text{concat}(a_n, b_m) = (a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_m)$$

我们用一个严格递增的序列：

$$\large o_{k} = (o_{k, s})_{s \in \{1, 2, \cdots, t\}} = (o_{k,1}, o_{k,2}, \cdots, o_{k, t})$$

表示从前 $k \in \{1, 2, \cdots, N\}$ 个物品中选择 $t \in \{0, 1,\cdots, k\}$ 个物品的一种选法，其中 $1 \leqslant o_{k, s} \leqslant k, \ o_{k, 1} < o_{k, 2} < \cdots < o_{k, t}$ 表示在这种选法中，被选中的第 $s$ 个物品是原来第 $o_{k, s}$ 个物品。

用一个序列的集合：

$$\large O_k = \left\{o_k \ \middle| \ o_{k} = (o_{k,1}, o_{k,2}, \cdots, o_{k, t}), \ 1 \leqslant o_{k, s} \leqslant k, \ o_{k, 1} < o_{k, 2} < \cdots < o_{k, t} \right\}$$

表示所有合法 $o_k$ 的集合。

用一个序列的集合：

$$\large S_{ij} = \left\{o_i \ \middle| \ \sum_{s = 1}^t v_{o_{i,s}} \leqslant j\right\}$$

表示从前 $i$ 个物品中选，且体积总和小于等于 $j$ 的所有选法集合。

用集合的集合：

$$\large \mathcal{S} = \left\{S_{ij} \ \middle| \ i \in \{1, 2, \cdots, N\}, \ j \in \{0, 1, \cdots, V\} \right\}$$

把所有合法的 $S_{ij}$ 打包为一个大集合。

用一个函数：

$$\large g: \mathcal{S} \rightarrow \mathbb{N} \quad g(S_{ij}) = \max_{o_i \in S_{ij}} \sum_{s=1}^t w_{o_{i,s}}$$

表示从前 $i$ 个物品中选，且体积总和小于等于 $j$ 的所有选法中选中的物品价值和的最大值。

设二元函数：

$$\large f: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N} \quad f(i, j) = g(S_{ij})$$

算法分析

考虑拆分问题，对于第 $k$ 个物品只有选或不选两种选择。设序列 $o_{k - 1} = (o_{k-1, 1}, o_{k-1,2}, \cdots, o_{k-1,t})$ 表示从前 $k - 1$ 个物品中选择的某一种选法。现在考虑第 $k$ 个物品，如果选择了第 $k$ 个物品，那么序列 $o_k = (o_{k-1, 1}, o_{k-1,2}, \cdots, o_{k-1,t}, k)$ 将会是一个从前 $k$ 个物品中选择的一个选法，如果不选第 $k$ 个物品，那么序列 $o'_k = (o_{k-1, 1}, o_{k-1,2}, \cdots, o_{k-1,t}) = o_{k - 1}$ 将会是一个从前 $k$ 个物品中选择的一个选法。于是可以选择使用动态规划，把大问题分解成多个小问题，在计算完所有小问题的答案之后，汇总这些答案，得到大问题的答案。

现在考虑如何计算 $g(S_{ij})$. 如果我们能够把 $S_{ij}$ 划分为 $u$ 个不相交的子集 $A_1, A_2, \cdots, A_u$，即 $p \neq q \rightarrow A_p \cap A_q = \emptyset$ 其中 $p, q \in \{1, 2, \cdots, u\}$，使得 $A_1 \cup A_2 \cup \cdots \cup A_u = S_{ij}$，那么我们就能轻松地计算出:

$$g(S_{ij}) = \max_{p \in \{1, 2, \cdots, u\}}g(A_p)$$

根据刚刚的拆分思路，我们将 $S_{ij}$ 按照第 $i$ 个物品有没有被选中拆分成两个集合：

$$A_1 = \left\{o_i \ \middle| \ o_{i,t} = i\right\}, \ A_2 = \left\{o_i \ \middle| \ o_{i,t} \neq i\right\}$$

$A_1$ 表示所有选中了第 $i$ 个物品的选法集合，$A_2$ 表示所有没有选中第 $i$ 个物品的选法集合。由于 $A_2$ 中的选法只从前 $i - 1$ 个物品中选择，有：

$$A_2 = S_{i-1, j}$$

所以

$$g(A_2) = g(S_{i-1, j})$$

观察 $A_1$ 的元素 $o_i$，$o_i$ 形如 $(o_{i,1}, o_{i,2}, \cdots, o_{i, t-1}, i)$. 这个序列的前 $t - 1$ 项不会出现 $i$，即前 $t - 1$ 项只会从前 $i - 1$ 个物品中选择，所以 $(o_{i,1}, o_{i,2}, \cdots, o_{i, t-1}) \in O_{i - 1}$. 由于 $S_{ij}$ 总体积和小于等于 $j$ 的要求：

$$\large \sum_{s = 1}^t v_{o_{i,s}} \leqslant j$$

对于任意一个 $A_1$ 的元素 $o_i = (o_{i,1}, o_{i,2}, \cdots, o_{i, t-1}, i)$ 有：

$$\large \sum_{s = 1}^t v_{o_{i,s}} = \sum_{s = 1}^{t - 1} v_{o_{i,s}} + v_i\leqslant j$$

故

$$\large \sum_{s = 1}^{t - 1} v_{o_{i,s}}\leqslant j - v_i$$

即除去最后一个 $i$ 物品，前 $t - 1$ 个选中的物品的体积和满足小于等于 $j - v_i$. 再加上刚刚得到的 $(o_{i,1}, o_{i,2}, \cdots, o_{i, t-1}) \in O_{i - 1}$，我们有 $(o_{i,1}, o_{i,2}, \cdots, o_{i, t-1}) \in S_{i - 1, j - v_i}$. 即除去最后一个 $i$ 物品的子序列是一个在前 $i - 1$ 个物品中选，体积和不超过 $j - v_i$ 的选法序列。反过来，显然任意一个 $S_{i-1, j-v_i}$ 中的序列 $o_{i-1}$，在末尾拼接上 $i$ 之后，就成为 $A_1$ 中的某个序列 $o_i$，即 $\text{concat}(o_{i-1}, (i)) \in A_1$。所以：

$$g(A_1) = g(S_{i - 1, j - v_i}) + w_i$$

所以

$$g(S_{ij}) = \max(g(S_{i - 1, j - v_i} + w_i), \ g(S_{i - 1, j}))$$

即

$$f(i, j) = \max(f(i - 1, j - v_i) + w_i, \ f(i - 1, j))$$

朴素的实现

注意到只有当 $j \geqslant v_i$ 时才有 $A_1 \neq \emptyset$.

const int N = 1010;

int f[N][N];
int v[N], w[N];

int main() {
    int n, V;
    cin >> n >> V;
    
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= V; j++) {
            f[i][j] =  f[i - 1][j];
            if (j - v[i] >= 0) {
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    cout << f[n][V] << endl;
}

优化的实现

由于 $f(i, j)$ 的计算只用到了 $f(i - 1, *)$，只需要保存前一轮次的计算结果 $f(i - 1, *)$. 于是可以省去 f 数组的第一个维度。注意到 f[j - v[i]] 在数组中的位置比 f[j] 靠前，如果正着枚举 j 会导致计算 f[j] 时 f[j - v[i]] 已经被更新，即 f[j - v[i]] 等于 $f(i, j - v_i)$ 而不是我们需要的 $f(i - 1, j - v_i)$. 所以枚举第二维 j 的时候需要倒着枚举。

int f[N];
int v[N], w[N];

int main() {
    int n, V;
    cin >> n >> V;
    
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = V; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[V] << endl;
}