历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

背包DP合集

作者：

一只野生彩色铅笔 , 2021-06-30 23:46:59 , 所有人可见 , 阅读 3147

106

144

背包DP合集

前言：背包DP 属于 线性DP 中的一种经典模型，围绕容量、物品、体积、价值等关键字展开

求解的是一种符合题设要求的 选择物品 的方案

1. 背包DP概述

背包问题的常见描述：

有 $N$ 件物品和一个总容量为 $V$ 的背包
第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$
找出一种选择物品的方案，使得选择的物品的总体积不超过 $V$，且 总价值 最大

然后针对于不同的 背包类型，对于选择物品的方式有着各式各样的 限制性条件，接下来一一列举

2. 01背包

限制性条件： 每件物品 只能选择一次

01背包 是所有 背包模型 中，最为简单的一种模型。正如他的名字一样，不选(0)或是选(1)的背包模型。

常用的 01背包 DP分析如下：

状态表示$f_{i,j}$—集合： 考虑前 i 个物品，且当前已使用体积不超过 j 的方案
状态表示$f_{i,j}$—属性： 该方案的价值为最大值 $\max$
状态转移$f_{i,j}$： $f_{i,j} = \max\Big(f_{i-1,j}, f_{i-1,j-v_i}+w_i\Big)$

常用的 01背包 优化方式是 空间优化

因为对于 i 阶段的状态 $f_{i,j}$ 来说，他的 状态转移 只会依赖 i-1 层的状态 $f_{i-1,j}$ 和 $f_{i-1,j-v_i}$

因此我们可以把空间优化到一维，直接用 $f_j$ 表示 处理当前物品时，总体积不超过 j 的方案

优化后的 状态转移方程 如下：
$$ f_j = max\Big(f_j, f_{j - v_i} + w_i\Big) $$
核心代码如下：

for (int i = 1; i <= n; ++ i)
    for (int j = m; j >= v[i]; -- j)//注意迭代的顺序，i层状态要用i-1层的旧状态更新
        f[j] = max(f[j], f[j - v[i]] + w[i]);

01背包 经典题目汇总：(顺序按难度递增)

3. 完全背包

限制性条件： 每件物品 可以使用无限多次

完全背包 也是 背包模型 中的经典模型，也是仅次于 01背包的最简单的一种 背包模型

因为每件物品可以使用 无限多次 而得名

常用的 完全背包 DP分析如下：

状态表示$f_{i,j}$—集合： 考虑前 i 个物品，且当前已使用体积不超过 j 的方案
状态表示$f_{i,j}$—属性： 该方案的价值为最大值 $\max$
状态转移$f_{i,j}$： $f_{i,j} = \max_{k=0}^{+\infty}\Big(f_{i-1,j-k\times v_i}+k\times w_i\Big)$

上述状态转移方程直接计算的话，最坏情况下的时间复杂度是 $O(N \times V^2)$

通过观察可以发现，状态 $f_{i,j}$ 的更新依赖 $f_{i-1,j}$ 和 $f_{i,j-v_i}+w_i$

也可以通过如下递推式获得上述结论：
$$ \begin{matrix} f(i, j) = \max\Big( f(i-1,j) &,& f(i-1,j-v_i)+w_i &,& \cdots &,& f(i-1,j-sv_i)+sw_i \Big)\\\ f(i, j-v_i) = \max\Big( &&f(i-1, j-v_i) &,& \cdots &,& f(i-1,j-sv_i)+{(s-1)w_i}\Big) \end{matrix} $$
因此 状态转移$f_{i,j}$ 可以优化为：$f_{i,j} = \max\Big(f_{i-1,j}, f_{i, j-v_i}+w_i\Big)$

这样，时间复杂度 就是 $O(N \times V)$ 了

空间上，优化思路和 01背包 类似，可以优化掉一维的空间

优化后的 状态转移方程 如下：
$$ f_{j} = \max\Big(f_{j}, f_{j-v_i}+w_i\Big) $$
核心代码 如下：

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

完全背包 经典题目汇总：(顺序按难度递增)

4. 多重背包

限制性条件： 每件物品 只能被使用有限多次

多重背包 在原来 完全背包 中额外限制了每个物品的 最多使用次数 是 $s_i$

因此原来完全背包的 优化无效

常用的 多重背包 DP分析如下：

状态表示$f_{i,j}$—集合： 考虑前 i 个物品，且当前已使用体积不超过 j 的方案
状态表示$f_{i,j}$—属性： 该方案的价值为最大值 $\max$
状态转移$f_{i,j}$： $f_{i,j} = \max_{k=0}^{s_i}\Big(f_{i-1,j-k\times v_i}+k\times w_i\Big)$

时间复杂度：$O(N \times V \times \sum s_i)$

二进制分组优化

把 多重背包 转化为 多个01背包 来求解

$O(N \times V)$ 是背包的最快时间复杂度，因此我们可以优化的就是 $O(\sum s_i)$

常识告诉我们，任意的 十进制数 可以通过进制转换变成 二进制比特串

我们可以把当前的物品数 $s_i$ 拆分成 能且仅能 表示 $[0,s_i]$ 所有数的几个 01物品

这样，从前往后做一遍 01背包DP 便可以求解本题

具体就是令 $A_{i,j} ~(j\in [0, \lfloor\log_2(s_i+1)\rfloor - 1])$ 分别表示由 $2^j$ 个物品 $i$ 捆绑而成的大物品

特殊地，若 $s_i+1$ 不是 $2$ 的整数次幂，则需要最后添加由 $s_i-2^{\lfloor\log_2(s_i+1)\rfloor-1}$ 个物品 $i$ 捆绑而成的大物品补足

举几个简单的例子：

6 = 1 + 2 + 3
8 = 1 + 2 + 4 + 1
18 = 1 + 2 + 4 + 8 + 3
31 = 1 + 2 + 4 + 8 + 16

二进制分组优化代码

for (int i = 1; i <= n; ++i)
{
    int a, b, s;
    scanf("%d%d%d", &a, &b, &s);
    int k = 1;
    while (k <= s)  //二进制拆分
    {
        ++cnt;
        v[cnt] = k * a;
        w[cnt] = k * b;
        s -= k;
        k *= 2;
    }
    if (s)  //补足剩余部分
    {
        ++cnt;
        v[cnt] = s * a;
        w[cnt] = s * b;
    }
}

单调队列优化

这个我在之前的某篇题解里详细写过

具体可以看 AcWing 6. 多重背包问题 III【单调队列优化+图示】

多重背包 经典题目汇总：(顺序按难度递增)

5. 混合背包

混合背包就是对 01背包、完全背包、多重背包 三者的结合

对于第 $i$ 种物品

可能最多只能使用 $1$ 次(01背包)
最多只能使用 $s_i$ 次(多重背包)
可以无限次使用(完全背包)

对于已经学会前三种背包的读者来说，这个就很简单了，对于不同种类，处理不同的状态转移即可

核心代码如下：

for (物品i)
{
    if (是 01背包)
        套用01背包代码;
    else if (是 完全背包)
        套用完全背包代码;
    else if (是 多重背包)
        套用多重背包代码
}

混合背包 经典题目汇总：(顺序按难度递增)

AcWing 7. 混合背包问题【混合背包DP模型】

6. 分组背包

限制性条件： 第 $i$ 个物品是一个物品组，里面有 $s_i$ 个物品，但是在物品组 $i$ 中最多只能选一个物品

01背包 是相对于全局，当前物品最多选一件物品；而 分组背包 是相对于物品组 $i$ ，当前物品最多选一件

因此我们直接在每个物品组中套用一遍 01背包 的 状态转移 即可

核心代码如下：

for (int i = 1; i <= n; ++ i)
    for (int j = m; j >= 0; -- j)
        for (int k = 1; k <= s[i]; ++ k)
            if (v[i][k] <= j)
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

分组背包 经典题目汇总：(顺序按难度递增)