【动态规划】背包问题合集

更新于 分类于 ， 阅读次数： 本文字数： 5.4k 阅读时长 ≈ 5 分钟

背包问题是动态规划的经典问题，题型灵活

一些说明

  • 背包问题总的来说，对于一个有限制条件（如体积、重量等，以及必须装满/可以不装满等要求）的背包，用一种策略选择物品装入，使得背包中的物品总价值最大。
  • 常规背包问题初始化：要求背包恰好装满体积 VV ：初始化为 INFINF ；最多不超过体积 VV ：初始化为 00
  • 开始可做的优化：去掉大于背包体积的物品
  • 参考资料：背包九讲

01背包

设定

  • 共 nn 件物品，第 ii 件物品的体积为 c(i)c(i) ，价值为 w(i)w(i) ，每件物品只有一个

分析

  • 记 f(i,v)f(i,v) 为前 ii 件物品放入体积为 vv 的背包中的能获得的最大价值

  • f(i,v)=max[f(i−1,v),f(i−1,v−c(i))+w(i)]f(i,v)=max[f(i-1,v),f(i-1,v-c(i))+w(i)]

  • 即用第 ii 件的信息更新 ff 时，比较不取第 ii 件的最大价值 f(i−1,v)f(i-1,v) 与取第 ii 件的最大价值 f(i−1,v−c(i))+w(i)f(i-1,v-c(i))+w(i) （前提是背包的体积 vv 能装下第 ii 件物品）

  • 伪代码：空间复杂度 O(NV)O(NV) ，时间复杂度 O(NV)O(NV)

1
2
3
4
5
6
f(i,v)=max(f(i-1,v),f(i-1,v-c(i))+w(i)) 
for i=1 to N
    for v=c(i) to V
        f(i,v)=max(f(i-1,v),f(i-1,v-c(i))+w(i))
    for v=0 to c(i)-1
        f(i,v)=f(i-1,v)     //  v从0到c(i)-1部分直接从i-1更新过来

空间复杂度优化

  • 省去第一维：设 f(v)f(v) 为当下（与遍历到哪件物品有关）背包体积为 vv 时的最大价值

  • 思想：注意到 ii 只能由 i−1i-1 的状态更新过来，因此只要保证更新时 ff 值还是上次更新的值就可以了，第二层循环要从大往小刷，则状态转移所需的 f(v−c(i))f(v-c(i)) 在第 ii 轮还未被更新，仍是第 i−1i-1 轮更新后的值

  • 伪代码：

1
2
3
for i=1 to N
    for v=V to c(i)
        f(v)=max(f(v),f(v-c(i))+w(i))
  • 这也是01背包最常见的写法，为方便其他背包变式，在这定义ZeroOnePack(f, c, w) 为以下内容（01背包的精髓）：
1
2
for v=V to c(i)
    f(v)=max(f(v),f(v-c(i))+w(i))

完全背包

设定

  • 共 nn 件物品，第 ii 件物品的体积为 c(i)c(i) ，价值为 w(i)w(i) ，每件物品有无限个

分析

  • f(i,v)f(i,v) 为前 ii 件放入体积为 vv 的背包中的最大价值

  • 可化成有 ⌊vc⌋\lfloor{\frac{v}{c}}\rfloor 件某相同物品的01背包

  • 开始可做优化：c(i)>c(j)&&w(i)<w(j)c(i)>c(j)\&\&w(i)<w(j) 时舍弃物品 ii （能取无限件的情况下肯定不会选择一个体积更大且价值更小的物品的）

  • 状态转移方程 f(i,v)=max{f(i−1,v−k∗c(i))+k∗w(i)},k∈N,k∈[0,vc(i)]f(i,v)=max\{f(i-1,v-k*c(i))+k*w(i)\}, k\in N,k\in[0,\frac{v}{c(i)}] ，即考虑第 ii 件物品取 k=0,1,⋯k=0,1,\cdots 件的最大价值（不能超过体积上限 vv ）

  • 伪代码：空间复杂度 O(NV)O(NV) ，时间复杂度 O(NV2)O(NV^2)

1
2
3
4
5
for i=1 to N
    for i=0 to V
        f(i,v)=f(i-1,v)    // 第i件物品取0件
        for k=1 to v/c(i)  // 第i件物品取1,2,...件
            f(i,v)=max(f(i,v),f(i-1,v-k*c(i))+k*w(i))

优化

  • 与01背包思路相同，想优化空间，与01背包不同的是物品有无数件，则第二维对体积的遍历不需要倒序，已经拿过若干个当前物品的背包可以继续拿，这样同时也优化了时间的一维

  • 伪代码：

1
2
3
for i=1 to N
    for v=c(i) to V  
        f(v)=max(f(v),f(v-c(i))+w(i))
  • 其中后两行是完全背包的精髓，为方便后面使用，我们将其定义为 CompletePack(f,c,w)

多重背包

设定

  • 共 nn 件物品，第 ii 件物品的体积为 c(i)c(i) ，价值为 w(i)w(i) ，每件物品有 m(i)m(i) 个

分析

  • f(i,v)f(i,v) 为前 ii 件放入体积为 vv 的背包中的最大价值

  • 状态转移方程 f(i,v)=max{f(i−1,v−k∗c(i))+k∗w(i)},k∈[0,min(v/c(i),m(i))]f(i,v)=max\{f(i-1,v-k*c(i))+k*w(i)\}, k\in[0,min(v/c(i),m(i))]，kk 是取这件物品的个数，与上述完全背包类似，只是由于物品有个数限制取的个数上限需做修改，且不能做上述完全背包的提前排除物品的优化

优化

  • 20,21,⋯2k,m−2k+1+12^0,2^1,\cdots2^k,m-2^{k+1}+1 这些数能表示 [0,m][0,m] 中的任何一个数。

  • 将 m(i)m(i) 件物品 ii 拆成由 20,21,⋯2k,m−2k+1+12^0,2^1,\cdots2^k,m-2^{k+1}+1 件物品 ii 构成的新物品，体积分别为 20×c(i),21×c(i),⋯2k×c(i),(m−2k+1+1)×c(i)2^0\times c(i),2^1\times c(i),\cdots2^k\times c(i),(m-2^{k+1}+1)\times c(i) ，价值分别为 20×w(i),21×w(i),⋯2k×w(i),(m−2k+1+1)×w(i)2^0\times w(i),2^1\times w(i),\cdots2^k\times w(i),(m-2^{k+1}+1)\times w(i) ，于是这 ⌊log⁡n⌋+1\lfloor\log n\rfloor +1 件新物品（每件只有一个）的选择情况能够表达原来取 [0,m(i)][0,m(i)] 件物品 ii 的情况。

  • 因此进行上述拆分后，对所有新物品跑01背包即可。

  • 代码如下，时间复杂度 O(Nlog⁡V+V)O(N\log V+V) ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// v[i],w[i],m[i]分别表示第i件物品的体积，价值和可取数量
// V[i],W[i]为二进制拆分后的所有物品的体积和价值，即01背包的初始条件，编号[1,cnt]
for (int i = 1; i <= n; i++)
{
    cin >> v[i] >> w[i] >> m[i];
    int x = 1; // 二进制系数2^k
    while (x <= m[i])
    {
        V[++cnt] = v[i] * x;
        W[cnt] = w[i] * x;
        m[i] -= x;
        x <<= 1;
    }
    if (m[i] > 0) // m-2^{k+1}+1
    {
        V[++cnt] = v[i] * m[i];
        W[cnt] = w[i] * m[i];
    }
}
ZeroOnePack(f, V, W);

为方便后面描述，我们将上述代码的逻辑过程 MultiplePack(f,c,w)

混合背包

  • 设定：共 nn 件物品，第 ii 件物品的体积为 c(i)c(i) ，价值为 w(i)w(i) ，每件物品有 m(i)m(i) 个或无限个

  • 分析：不同类型的物品按不同类型处理即可

  • 伪代码：

1
2
3
4
5
6
7
for i=1 to N
    if 第i件是01背包
        ZeroOnePack(f,c,w)
    else if 第i件是完全背包
        CompletePack(f,c,w)
    else if 第i件是多重背包
        MultiplePack(f,c,w,m)

二维费用的背包

  • 设定：背包有两个限制条件 V,UV,U （比如体积和重量），共 nn 件物品，第 ii 件物品的代价（比如体积和重量）为 c(i),d(i)c(i),d(i) ，价值为 w(i)w(i) ，物品的选择可能是01/完全/多重/混合背包
  • 状态设定：f(i,v,u)f(i,v,u) 为前 ii 件放入限制条件为 v,uv,u 的背包中的最大价值，状态转移方程要结合具体背包类型来写（与二维一样）。以01背包为例，f(i,v,u)=max[f(i−1,v,u),f(i−1,v−c(i),u−d(i))+w(i)]f(i,v,u)=max[f(i-1,v,u),f(i-1,v-c(i),u-d(i))+w(i)]
  • 优化：结合具体背包类型来写，与二维一样，只是扩展了维数而已
  • 继续扩展：增加限制条件→\rightarrow 增加维数

分组背包

  • 设定：共 nn 件物品，第 ii 件物品的体积为 c(i)c(i) ，价值为 w(i)w(i) ，每件物品只有 11 个。这些物品被划分成 KK 组，组中物品最多选一件。
  • 分析：显然组内是一个01背包，设 f(k,v)f(k,v) 表示第 kk 组用体积为 vv 的背包，能获得的最大价值（即普通01背包加了一维第几组）。这样每一组便又是一个01背包，代码可以写在一起（反正都是从大到小遍历背包体积）
  • 伪代码：
1
2
3
4
5
6
7
for k=1 to K
    for v=V to 0           // 组间01背包
        for item i in k    // 组内01
            if(v>=c(i))
                f(v)=max(f(v),f(v-c(i))+w(i)) 
                // 此时用的是k-1组的价值更新
                // 对于同一个v，第k组内的物品至多只有一个被选上（因为一直在取max）

有依赖的背包

设定

  • 共 nn 件物品，第 ii 件物品的体积为 c(i)c(i) ，价值为 w(i)w(i)

  • 物品间存在特定依赖关系：如果选择物品 xx ，必须选择物品 yy ；反之如果选择物品 yy ，不一定选择物品 xx。将 xx 称主件，yy 称附件。

  • 不存在一个物品依赖多个物品（即如果选择物品 xx ，必须选择的物品最多只有一个）

分析

  • 可以看出依赖关系是一个树形关系

  • 以一个节点和它的子节点看作一组，先处理出这些节点的所有背包体积的对应价值，上一层再对这些组进行分组背包中的组选择

  • 设 dp[u][c]dp[u][c] 表示 uu 节点（及其子孙节点整体）放在体积为 cc 的背包能获得的最大价值

  • 遍历 uu 的所有子节点 vv ，更新 dp[u]dp[u] ，此时它代表的内容是不包括 uu 对应背包各种体积能获得的最大价值

  • 遍历完后，对于背包空间足够放下 uu 这个物品的，全部强制放入 uu （依赖项必须得选），空间不足的背包价值清零

  • 代码：时间复杂度 O(NV2)O(NV^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> G[N]; // 邻接矩阵存树
int dp[N][M];
int c[N], w[N]; // 体积、价值
void dfs(int rt, int from)
{
    for (auto v : G[rt]) // 遍历子节点
    {
        if (v == from)
            continue;
        for (int i = V - c[rt]; i >= 0; i--) // 体积V的背包，01背包优化一维空间（倒序），不足c[rt]空间的可以不考虑
            for (int j = 0; j <= i; j++)     // 子节点已经得到的体积j的背包
                dp[rt][i] = max(dp[rt][i], dp[rt][i - j] + dp[v][j]);
    }
    for (int i = V; i >= c[rt]; i++)
        dp[rt][i] = dp[rt][i - c[rt]] + w[rt];
    for (int i = 0; i < c[rt]; i++)
        dp[rt][i] = 0;
}

特例

[NOIP2006 提高组] 金明的预算方案](https://www.luogu.com.cn/problem/P1064) 这道题由于规定了主件个数 0,1,20,1,2 ，所以直接强行分类讨论就好了，并不一定要树形dp