背包问题

总任务：求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

动态规划问题一般没有算法模板。

0-1背包问题

条件：有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品最多只能使用一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

例题：01背包问题的朴素解法

最大价值是物品数量 $i$ 和背包容量 $j$ 的函数，设函数 $f(i,j)$ 表示前 $i$ 件物品放入容量为 $j$ 的背包的最大价值，最终的最大价值就是物品数量 $i$ 从 $0$ 增长到 $N$，背包容量 $j$ 从 $0$ 增长到 $V$ 时的 $f(N,V)$ 值。

动态规划 $D_p$ 常用如下模型进行分析：

• 状态表示： $f(i,j)$ 是前 $i$ 个物品，背包容量 $j$ 下的最优解(最大价值)：
  • 集合：是所有选法的集合，需要满足如下两个条件：
    • 只从前 $i$ 个物品当中选；
    • 选出物品的总体积 $⩽j$。
  • 属性：是一个数值，一般代表所有选法总价值的最大值 ${\mu }_{max}$，最小值 ${\mu }_{min}$，或元素数量等(本题为最大值)。
• 状态计算：最终答案是 $f(N,V)$，一般对应集合的划分。本问题可将集合划分为从物品 $1$ 到 $i-1$ 中选择的总体积不超过 $j$ 的不含 $i$ 的集合( $f(i-1,j)$ )以及物品含 $i$ 的集合( $f(i-1,j-v_i)+w_i$ )，共两个子集；集合划分需满足如下原则：
  • 不重：一般要满足；
  • 不漏：必须要满足。

注意以上“含 $i$ 的集合”指的是从物品 $1$ 到 $i-1$ 中选择的总体积不超过 $j-v_i$ 的选法的集合，也就是 $f(i-1,j-v_i)+w_i$。

可以得到：

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

进一步写出完整的递推式：

$$f(i,j)=\{\begin{array}{l}f(i-1,j),j<v\left[i\right]\\ max[f(i-1,j),f(i-1,j-v\left[i\right])+w\left[i\right]],j⩾v\left[i\right]\end{array}$$

其中 $f(i,0)=0;(1⩽i⩽N)$，且 $f(0,j)=0;(1⩽j⩽V)$，可见 $f(i,j)$ 应该全 $0$ 初始化，可以声明为全局变量。

模板：

for (int i = 1; i <= n; i++) {  // 物品i
    for (int j = 1; j <= m; j++) {  // 容量j
        if (j < v[i]) f[i][j] = f[i - 1][j];
        else
            f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
    }
}
cout << f[n][m] << endl;

时间和空间复杂度均为 $O(N\cdot V)$，时间复杂度不能降低了，但空间复杂度还可以降为一维。是否可以用一维数组f[j]只记录一行数据，让 $j$ 值顺序循环，顺序更新f[j]呢？答案是不行，因为如果 $j$ 是顺序循环，f[j - v[i]]会先于f[j]更新，即用新值f[j - v[i]]去更新f[j]会出错。

$D_p$ 优化指的是对已有 $D_p$ 的代码、方程进行优化。

例题：01背包问题的一维优化

将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的 $i$ 与 $j$ 最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

状态f[j]$定义： $N$ 件物品，背包容量 $j$ 下的最优解。注意枚举背包容量 $j$ 必须从 $m$ 开始。用一维数组f[j]只记录一行数据，让 $j$ 值逆序循环，逆序更新f[j]的值。f[j]称为滚动数组。因为 $j$ 是逆序循环，f[j]会先于f[j-w[i]]更新，即用旧值f[j-w[i]]去更新f[j]，才可以得到正确的结果。

模板：

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 1; j--) {  // 这里是逆序循环
        if (j < v[i]) f[j] = f[j];
        else f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}

这个视频 讲解较好。

完全背包问题

条件：有 $N$ 个物品和一个容量是 $V$ 的背包。每个物品都有无限件可用。第 $i$ 个物品的体积是 $v_i$，价值是 $w_i$。

动态规划问题：

• 状态表示：
  • 集合： $f(i,j)$表示考虑前 $i$ 个物品且总体积不大于 $j$ 的所有选法；
  • 属性：所有选法的最大价值。
• 状态计算：集合的划分，按照第 $i$ 个物品选了多少个可以分为若干组，设第 $i$ 个物品选了 $k$ 件，可按如下步骤进行计算：
  • 去掉 $k$ 件物品 $i$；
  • 求最大值： $f(i-1,j-k\cdot v[i])$；
  • 再加回来 $k$ 件物品 $i$。

状态转移方程为：

$$f(i,j)=max[f(i,j),f(i-1,j-k\cdot v\left[i\right])+k\cdot w\left[i\right]]$$

更完整地，设第 $i$ 种物品最多能选 $t$ 个，可知 $t=\lfloor \frac{j}{v\left[i\right]}\rfloor$，其中 $j$为当前容量，则可得完整递推式：

$$f(i,j)=\underset{0⩽k⩽t}{max}f(i-1,j-k\cdot v\left[i\right])+k\cdot w\left[i\right]$$

例题：完全背包问题的朴素解法

朴素解法时间复杂度为 $O\left(V^{2}N\right)$。

为了优化朴素解法，可以观察原递推方程：

$$f(i,j-v\left[i\right])=max[f(i-1,j-v\left[i\right]),f(j-1,j-2\cdot v\left[i\right])+w\left[i\right],$$

$$f(j-1,j-3\cdot v\left[i\right])+2\cdot w\left[i\right],\cdots ];$$

$$f(i,j)=max[f(i-1,j),f(i-1,j-v\left[i\right])+w\left[i\right],$$

$$f(j-1,j-2\cdot v\left[i\right])+2\cdot w\left[i\right],f(j-1,j-3\cdot v\left[i\right])+3\cdot w\left[i\right],\cdots ]$$

$$=max[f(i-1,j),f(i,j-v\left[i\right])+w\left[i\right]]$$

简化得：

$$f(i,j)=max[f(i-1,j),f(i,j-v\left[i\right])+w\left[i\right]]$$

这种递推优化的解法就不用再枚举 $k$ 重循环了，时间复杂度为 $O(NV)$。

例题：完全背包问题的递推优化

另一种视角：

当前背包容量为 $j$，要考虑第 $i$ 件物品能否放入，是否放入。

• 当前背包容量 $j<v[i]$，不能放入，则 $f(i,j)=f(i-1,j)$；
• 当前背包容量 $j⩾v[i]$，能放入，但要比较代价：
  • 若第 $i$ 件物品不放入背包，则 $f(i,j)=f(i-1,j)$；
  • 若第 $i$ 件物品放入背包，则 $f(i,j)=f(i,j-v[i])+w[i]$。

解释：对于前 $i$ 件物品，背包容量为 $j-v[i]$ 时可能已经放入了第 $i$ 件物品，容量为 $j$ 时还可以再放入第 $i$ 件物品，所以用 $f(i,j-v[i])$ 更新 $f(i,j)$ (注意这里与0-1背包的不同)。

综上：

$$f(i,j)=\{\begin{array}{l}f(i-1,j),j<v\left[i\right];\\ max[f(i-1,j),f(i,j-v\left[i\right])+w\left[i\right]],j⩾v\left[i\right]\end{array}$$

模板：

for (int i = 1; i <= n; i++) {  // 物品i
    for (int j = 1; j <= m; j++) {  // 容量j
        if (j < v[i]) f[i][j] = f[i - 1][j];
        else
            f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
    }
}
cout << f[n][m] << endl;

类似地，完全背包问题也可以优化到一维空间复杂度。上式对应的是 $j$ 从小到大遍历，于是我们只需把0-1背包问题的代码中的 $j$ 改为从小到大遍历即可。不用由大到小遍历，因为要的就是覆盖的效果！

例题：完全背包问题的一维优化

一维优化解法的时间复杂度不变，空间复杂度降为 $O(V)$。

注意这里完全背包的j的循环顺序和0-1背包不同。因为j是顺序循环，f[j-v[i]]会先于f[j]更新，也就是说用新值f[j-v[i]]去更新f[j]，相当于用第i行的f[j-v[i]]值更新f[j]，所以可以顺序循环。

模板：

for (int i = 1; i <= n; i++) {  // 物品i
    for (int j = 1; j <= m; j++) {  // 容量j (这里是顺序循环)
        if (j < v[i]) f[j] = f[j];
        else
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}
cout << f[m] << endl;

进一步优化(j从v[i]开始循环)：

for (int i = 1; i <= n; i++) {  // 物品i
    for (int j = v[i]; j <= m; j++) {  // 容量j
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}

多重背包问题

条件：有 $N$ 件物品和一个容量是 $V$ 的背包。第 $i$ 种物品最多有 $s_i$ 件。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

动态规划问题：

• 状态表示： $f(i,j)$
  • 集合：所有只从前 $i$ 个物品中选择，并且总体积不超过 $j$ 的选法；
  • 属性：集合中每个选法对应的总价值的最大值。
• 状态计算：根据第 $i$ 个物品选了多少个来划分集合(可选 $0$ 个， $1$ 个，...，直到 s[i]个)。

状态转移方程：

$$f(i,j)=max[f(i-1,j-v\left[i\right]\cdot k)+w\left[i\right]\cdot k];k=0,1,2,\cdots ,s\left[i\right]$$

例题：多重背包问题的朴素解法

模板：

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
            f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
        }
    }
}
cout << f[n][m] << endl;

朴素解法一维空间优化的模板：

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {
        for (int k = 0; k <= s[i] && k * v[i] <= j; k++)
            f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
    }
}
cout << f[m] << endl;

朴素解法时间复杂度为 $O(NVS)$。

我们不能直接用完全背包问题的优化方法来优化多重背包问题，因为max操作不具有可减性。可以采用二进制优化。

引论：如何将正整数 $s$ 用类似二进制的方式表示？选择 $1,2,4,8,\cdots ,2^k,c$ 这些数字进行相加(每个数字最多选一次)，其中 $2^k⩽s,2^{k+1}>s$，且 $c<2^{k+1}$；它们(除了 $c$ 外)可以凑出 $0\sim 2^{k+1}-1$ 之间的数，加上 $c$ 后可以凑出 $c\sim 2^{k+1}-1+c=s$ 之间的数，要求区间 $[0,2^{k+1}-1],[c,s]$中间不能有缝隙，事实上因为 $c<2^{k+1}$ 显然成立。故从 $0$ 到 $s$ 的所有数可以拼接出来。

举例：水果店里有 $40$ 个苹果，小明计划购买 $n(1⩽n⩽40)$ 个苹果，如何让小明尽可能快速地完成购买？一个显而易见的暴力做法是，让小明一个个拿(单位是个)，但效率过于低下。事实上，店员可事先准备好 $6$ 个箱子，每个箱子中的苹果数量分别为 $[1,2,4,8,16,9]$，再让小明按箱子拿(单位是箱子)，无论小明计划购买多少个，他最多只需要拿 $6$ 次，而在暴力做法中，小明最多需要拿 $40$ 次。

用数学表达式，可以断定对任意的正整数 $s$，都可以找到 $\lfloor {\log }_{2}s\rfloor +1\triangleq k$ 个正整数 $a_1,a_2,\cdots ,a_k$，使得 $\mathrm{\forall }n\in [0,s]$，都有：

$$n={\mathit{v}}^T\cdot \mathit{a};\mathit{a}=\left[\begin{array}{c}{a}_1\\ ⋮\\ a_k\end{array}\right],a_i=\{\begin{array}{l}{2}^{i-1},\\ s-2^{i-1}+1;(\in [1,2^{k-1}])\end{array}$$

其中：

$$\mathit{v}=\left[\begin{array}{c}{v}_1\\ ⋮\\ v_k\end{array}\right]$$

且 $\mathit{v}$ 的每个分量要么是 $0$ 要么是 $1$。

现在对于每种物品 $i$，可以将这 $s[i]$ 个物品分散至 $\lfloor {\log }_{2}s\left[i\right]\rfloor +1$ 个箱子中，将多重背包便化成0-1背包，多重背包问题中的一个箱子相当于0-1背包问题中的一件物品。

二进制拆分思想：把第 $i$ 种物品拆分成若干件物品，每件物品的体积和价值乘以一个拆分系数 $(1,2^1,2^2,\cdots ,2^{k-1},s_i-2^k+1)$，就可以转化成0-1背包问题求解。例如：若 $s_i=12$，拆分系数为 $1,2,4,5$，转化成 $4$ 件0-1背包的物品： $(v_i,w_i),(2v_i,2w_i),(4v_i,4w_i),(5v_i,5w_i)$。

这样可以把时间复杂度从 $O(N\cdot V\cdot S)$ 变为 $O(N\cdot V\cdot \log S)$。

例题：多重背包问题的二进制优化

模板程序：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 25000;
const int M = 2010;

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

int main() {
    cin >> n >> m;
    int num = 1;
    for (int i = 1; i <= n; i++) {
        // v 体积  w 价值  s 数量
        int vi, wi, s;
        cin >> vi >> wi >> s;
        for (int k = 1; k <= s; k <<= 1) {  // k <<= 1 相当于 k *= 2
            v[num] = k * vi;
            w[num++] = k * wi;
            s -= k;
        }
        if (s > 0) {
            v[num] = s * vi;
            w[num++] = s * wi;
        }
    }

    for (int i = 1; i <= num - 1; i++) {
        for (int j = m; j >= v[i]; j--) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << endl;

    return 0;
}

分组背包问题

条件：有 $N$ 组物品和一个容量是 $V$ 的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号， $j$ 是组内编号。 $s_i$ 表示第 $i$ 个物品组的物品数量。

动态规划问题：

• 状态表示：
  • 集合：只从前 $i$ 组物品中选，且总体积不大于 $j$ 的所有选法；
  • 属性：最大值。
• 状态计算 (集合划分)：
  • 枚举第 $i$ 组物品选 哪个；
  • 如果不选第 $i$ 组第 $k$ 个物品： $f(i,j)$；
  • 如果选第 $i$ 组第 $k$ 个物品： $f(i-1,j-v[i,k])+w[i,k]$。

递推式：

$$f\left(j\right)=max[f\left(j\right),\underset{1⩽k⩽s\left[i\right]}{max}f(j-v[i,k])+w[i,k]]$$

例题：分组背包问题；分组背包问题一维优化

分组背包问题难以使用二进制或单调队列进行优化，但可以对空间进行一定的优化。

模板程序：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n, m, s;
int v[N], w[N];
int f[N];

int main() {
    cin >> n >>m;
    for (int i = 1; i <= n; i++) {  // 物品
        cin >> s;
        for (int j = 1; j <= s; j++) cin >> v[j] >> w[j];
        // 不能交换体积和决策的内外循环顺序！
        for (int j = m; j >= 0; j--) {  // 体积
            for (int k = 0; k <= s; k++) {  // 决策
                if (j >= v[k])
                    f[j] = max(f[j], f[j - v[k]] + w[k]);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}