C++ 动态规划 - 背包问题专题

C++ 动态规划 - 背包问题专题

前言

背包问题是动态规划中的经典问题，在算法竞赛和实际应用中都非常重要。本文将详细介绍各种背包问题的解法，包括01背包、完全背包、多重背包、分组背包等。

前置知识：

本文导航：

  • 📦 背包问题概述：什么是背包问题
  • 🎯 01背包问题：基础背包，每种物品最多选1次
  • ♾️ 完全背包问题：每种物品可以选无限次
  • 🔢 多重背包问题：每种物品有数量限制
  • 📚 分组背包问题：物品分组，每组最多选1个
  • 📊 四种背包问题对比：总结与记忆技巧
  • 💡 练习题推荐：巩固所学知识

背包问题概述

1. 什么是背包问题

背包问题是一类组合优化的NP完全问题，问题可以描述为：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择物品使得总价值最大。

背包问题的基本要素：

  • 物品：每个物品有重量（体积）和价值
  • 背包容量：背包能承受的最大重量（体积）
  • 目标：在不超过容量的前提下，使总价值最大

2. 背包问题的分类

背包类型 特点 典型问题
01背包 每种物品最多选1次 基础背包问题
完全背包 每种物品可以选无限次 硬币问题
多重背包 每种物品有数量限制 物品有库存限制
分组背包 物品分组，每组最多选1个 课程选择问题
混合背包 混合多种背包类型 综合问题
二维费用背包 有两个容量限制 体积+重量限制

01背包问题

1. 问题描述

01背包问题：有N个物品和一个容量为V的背包。每个物品只能使用一次。第i个物品的体积是 v[i]，价值是 w[i]。

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

特点：每种物品只有选或不选两种状态（0或1，因此称为01背包）

2. 问题分析

方法一：常规分析方法

常规分析方法是最常用的动态规划分析方法，通过以下步骤进行：

第一步：状态定义

  • dp[i][j] 表示前i个物品，在容量为j的背包中能获得的最大价值

第二步：状态转移方程

对于第i个物品，有两种选择：

  1. 不选第i个物品：dp[i][j] = dp[i-1][j]
  2. 选第i个物品：需要容量足够，dp[i][j] = dp[i-1][j-v[i]] + w[i]

状态转移方程：

1
2
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])  (j >= v[i])
dp[i][j] = dp[i-1][j]  (j < v[i])

第三步：初始状态

  • dp[0][j] = 0（没有物品，价值为0）
  • dp[i][0] = 0（容量为0，价值为0）

方法二：闫氏DP分析法

闫氏DP分析法是由算法竞赛教练闫学灿（yxc）总结的一种系统化的动态规划分析方法。这种方法通过集合的角度来理解动态规划，使问题分析更加清晰和系统化。

第一步：状态表示

  • 集合：dp[i][j] 表示所有只考虑前i个物品，且总体积不超过j的选法集合
  • 属性：集合中所有方案的最大价值

第二步：状态计算

将集合 dp[i][j] 划分为两个子集：

  1. 不选第i个物品：只考虑前i-1个物品，总体积不超过j

    • 对应集合：dp[i-1][j]
    • 价值：dp[i-1][j]

  2. 选第i个物品：只考虑前i-1个物品，总体积不超过 j-v[i]，然后加上第i个物品的价值

    • 对应集合：dp[i-1][j-v[i]]
    • 价值：dp[i-1][j-v[i]] + w[i]

状态转移方程：

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])

3. 算法实现

3.1 二维DP实现

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int f[N][N];  // f[i][j] 表示前i个物品，容量为j时的最大价值
int n, m;     // n个物品，背包容量为m
int v[N], w[N];  // v[i]表示体积，w[i]表示价值

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    // 【状态转移】
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 不选第i个物品
            f[i][j] = f[i - 1][j];
            
            // 选第i个物品（需要容量足够）
            if (j >= v[i]) {
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}

代码说明：

  • f[i][j] 表示前i个物品，容量为j时的最大价值
  • 外层循环遍历物品，内层循环遍历容量
  • 对于每个状态，考虑选或不选当前物品

3.2 一维DP优化（空间优化）

观察状态转移方程：dp[i][j] 只依赖于 dp[i-1][...]，即当前状态只依赖于上一行的状态。

因此可以使用滚动数组优化，将二维数组压缩为一维数组。

关键点：需要逆序遍历容量j，避免覆盖未使用的状态。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int f[N];  // f[j] 表示容量为j时的最大价值
int n, m;
int v[N], w[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    // 【状态转移】一维优化
    for (int i = 1; i <= n; i++) {
        // 【关键】逆序遍历容量，避免覆盖未使用的状态
        for (int j = m; j >= v[i]; j--) {
            // f[j] 表示不选第i个物品
            // f[j - v[i]] + w[i] 表示选第i个物品
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

为什么需要逆序遍历？

这是01背包一维优化的关键点，理解这一点非常重要！

正序遍历的问题

如果使用正序遍历（j从v[i]到m），会发生什么？

示例：有1个物品，体积v[1]=2，价值w[1]=3，背包容量m=4

正序遍历过程（错误示例）：

步骤 j f[j] 更新前 f[j-v[1]] f[j] 更新后 说明
1 2 f[2]=0 f[0]=0 f[2]=max(0, 0+3)=3 ✅ 正确：选择1个物品1
2 3 f[3]=0 f[1]=0 f[3]=max(0, 0+3)=3 ✅ 正确：选择1个物品1
3 4 f[4]=0 f[2]=3 f[4]=max(0, 3+3)=6 ❌ 错误：选择了2个物品1！

问题分析：

  • 当j=4时，f[2]已经被更新为3（表示已经选择了1个物品1）
  • 然后 f[4] = max(f[4], f[2] + w[1]) = max(0, 3+3) = 6
  • 这相当于在已经选择1个物品1的基础上，又选择了1个物品1，总共选择了2个
  • 违反了01背包”每种物品最多选1次”的规则

逆序遍历的正确性

使用逆序遍历（j从m到v[i]），可以避免这个问题。

逆序遍历过程（正确示例）：

步骤 j f[j] 更新前 f[j-v[1]] f[j] 更新后 说明
1 4 f[4]=0 f[2]=0 f[4]=max(0, 0+3)=3 ✅ 正确：选择1个物品1
2 3 f[3]=0 f[1]=0 f[3]=max(0, 0+3)=3 ✅ 正确：选择1个物品1
3 2 f[2]=0 f[0]=0 f[2]=max(0, 0+3)=3 ✅ 正确：选择1个物品1

正确性分析：

  • 当j=4时，f[2]还是0（未被更新），使用的是上一轮（前i-1个物品）的状态
  • f[4] = max(f[4], f[2] + w[1]) = max(0, 0+3) = 3
  • 这表示只选择了1个物品1，符合01背包的要求
  • 逆序遍历保证了 f[j-v[i]] 总是来自上一轮的状态

对比表格

正序遍历 vs 逆序遍历对比（以物品1，体积2，价值3为例）：

容量j 正序遍历 逆序遍历
f[j]更新前 f[j-v[1]]
2 0 f[0]=0
3 0 f[1]=0
4 0 f[2]=3 ❌

关键区别：

  • 正序：j=4时，f[2]已经被更新为3，导致物品1被选择了2次
  • 逆序：j=4时，f[2]还是0（未更新），保证物品1只被选择1次

详细原理说明

状态转移方程回顾：

1
f[j] = max(f[j], f[j - v[i]] + w[i])

关键理解：

  • f[j] 表示容量为j时的最大价值
  • f[j - v[i]] 应该是不包含当前物品i的状态
  • 在01背包中，每个物品只能选一次，所以 f[j - v[i]] 必须来自前i-1个物品的状态

逆序遍历的工作原理：

  1. 从大到小遍历容量：j = m, m-1, …, v[i]
  2. 状态更新顺序：先更新大容量，再更新小容量
  3. 状态依赖关系：更新 f[j] 时，f[j - v[i]] 还没有被当前物品更新过
  4. 保证正确性：f[j - v[i]] 始终是前i-1个物品的状态

正序遍历的错误原因：

  1. 从小到大遍历容量：j = v[i], v[i]+1, …, m
  2. 状态更新顺序：先更新小容量，再更新大容量
  3. 状态依赖问题：更新 f[j] 时，f[j - v[i]] 可能已经被当前物品更新过
  4. 导致错误：同一物品可能被选择多次

代码对比

错误写法（正序遍历）：

1
2
3
4
5
6
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]);
        // 当j较大时，f[j-v[i]]可能已经被当前物品更新过
    }
}

正确写法（逆序遍历）：

1
2
3
4
5
6
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {  // ✅ 逆序遍历
        f[j] = max(f[j], f[j - v[i]] + w[i]);
        // f[j-v[i]]始终是前i-1个物品的状态
    }
}

空间复杂度优化：从 O(n×V) 优化到 O(V)

4. 完整示例

题目：有4个物品，背包容量为5。物品信息如下：

物品 体积 价值
1 1 2
2 2 4
3 3 4
4 4 5

求解过程：

使用二维DP，状态转移表如下：

i\j 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 2 2 2 2 2
2 0 2 4 6 6 6
3 0 2 4 6 6 8
4 0 2 4 6 6 8

答案：最大价值为8（选择物品1和物品3）

5. 时间复杂度分析

  • 时间复杂度：O(n×V)
    • 需要遍历n个物品，每个物品需要遍历V个容量
  • 空间复杂度：
    • 二维DP：O(n×V)
    • 一维DP：O(V)

完全背包问题

1. 问题描述

完全背包问题：有N个物品和一个容量为V的背包。每个物品可以使用无限次。第i个物品的体积是 v[i]，价值是 w[i]。

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

特点：每种物品可以选择0次、1次、2次…无限次

2. 问题分析

方法一：常规分析方法

常规分析方法是最常用的动态规划分析方法，通过以下步骤进行：

第一步：状态定义

  • dp[i][j] 表示前i个物品，在容量为j的背包中能获得的最大价值

第二步：状态转移方程

对于第i个物品，可以选择0次、1次、2次…直到容量不够为止。

朴素思路（三层循环）：

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i], dp[i-1][j-2*v[i]] + 2*w[i], ...)

优化思路：
观察发现，dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])

状态转移方程：

1
2
dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])  (j >= v[i])
dp[i][j] = dp[i-1][j]  (j < v[i])

与01背包的区别：

  • 01背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
  • 完全背包：dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])

注意：完全背包使用的是 dp[i][j-v[i]]（当前物品可以继续选），而01背包使用的是 dp[i-1][j-v[i]]（当前物品只能选一次）

方法二：闫氏DP分析法

闫氏DP分析法是由算法竞赛教练闫学灿（yxc）总结的一种系统化的动态规划分析方法。这种方法通过集合的角度来理解动态规划，使问题分析更加清晰和系统化。

第一步：状态表示

  • 集合：dp[i][j] 表示所有只考虑前i个物品，且总体积不超过j的选法集合
  • 属性：集合中所有方案的最大价值

第二步：状态计算

将集合 dp[i][j] 按选择第i个物品的个数k进行划分：

  • 不选第i个物品：dp[i-1][j]
  • 选1个第i个物品：dp[i-1][j-v[i]] + w[i]
  • 选2个第i个物品：dp[i-1][j-2*v[i]] + 2*w[i]
  • 选k个第i个物品：dp[i-1][j-k*v[i]] + k*w[i]（k*v[i] <= j）

优化：通过数学推导，可以优化为：

1
dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])

3. 算法实现

3.1 二维DP实现（朴素版本）

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
#include <iostream>
using namespace std;

const int N = 1010;

int f[N][N];  // f[i][j] 表示前i个物品，容量为j时的最大价值
int v[N], w[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    // 【状态转移】三层循环版本
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // 枚举选择第i个物品的个数k
            for (int k = 0; k * v[i] <= j; k++) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }

    cout << f[n][m] << endl;
    return 0;
}

时间复杂度：O(n×V×k)，其中k是每个物品最多能选择的个数，效率较低。

3.2 二维DP优化版本

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
#include <iostream>
using namespace std;

const int N = 1010;

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

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    // 【状态转移】优化版本
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // 不选第i个物品
            f[i][j] = f[i - 1][j];
            
            // 选第i个物品（可以选多个）
            if (j >= v[i]) {
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
            }
        }
    }

    cout << f[n][m] << endl;
    return 0;
}

优化说明：

  • 使用 f[i][j - v[i]] 而不是 f[i-1][j - v[i]]
  • 这样可以在当前物品已经选择的基础上继续选择，实现”无限次”的效果

3.3 一维DP优化（空间优化）

与01背包类似，完全背包也可以使用一维数组优化。

关键点：需要正序遍历容量j，允许同一物品被选择多次。

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
#include <iostream>
using namespace std;

const int N = 1010;

int f[N];  // f[j] 表示容量为j时的最大价值
int v[N], w[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    // 【状态转移】一维优化
    for (int i = 1; i <= n; i++) {
        // 【关键】正序遍历容量，允许同一物品选择多次
        for (int j = v[i]; j <= m; j++) {
            // f[j] 表示不选第i个物品（或已经选过）
            // f[j - v[i]] + w[i] 表示再选一个第i个物品
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    
    cout << f[m] << endl;
    return 0;
}

为什么需要正序遍历？

这是完全背包一维优化的关键点，与01背包的逆序遍历形成鲜明对比！

逆序遍历的问题

如果使用逆序遍历（j从m到v[i]），会发生什么？

示例：有1个物品，体积v[1]=2，价值w[1]=3，背包容量m=4

逆序遍历过程（错误示例，对于完全背包）：

步骤 j f[j] 更新前 f[j-v[1]] f[j] 更新后 说明
1 4 f[4]=0 f[2]=0 f[4]=max(0, 0+3)=3 ✅ 正确：选择1个物品1
2 3 f[3]=0 f[1]=0 f[3]=max(0, 0+3)=3 ✅ 正确：选择1个物品1
3 2 f[2]=0 f[0]=0 f[2]=max(0, 0+3)=3 ✅ 正确：选择1个物品1

问题分析：

  • 当j=4时，f[2]还是0（未被更新），使用的是上一轮的状态
  • f[4] = max(f[4], f[2] + w[1]) = max(0, 0+3) = 3
  • 这表示只选择了1个物品1，无法实现”无限次”选择
  • 违反了完全背包”每种物品可以选无限次”的规则

正序遍历的正确性

使用正序遍历（j从v[i]到m），可以实现”无限次”选择。

正序遍历过程（正确示例）：

步骤 j f[j] 更新前 f[j-v[1]] f[j] 更新后 说明
1 2 f[2]=0 f[0]=0 f[2]=max(0, 0+3)=3 ✅ 正确：选择1个物品1
2 3 f[3]=0 f[1]=0 f[3]=max(0, 0+3)=3 ✅ 正确：选择1个物品1
3 4 f[4]=0 f[2]=3 f[4]=max(0, 3+3)=6 ✅ 正确：选择2个物品1！

正确性分析：

  • 当j=4时，f[2]已经被更新为3（表示已经选择了1个物品1）
  • f[4] = max(f[4], f[2] + w[1]) = max(0, 3+3) = 6
  • 这表示在已经选择1个物品1的基础上，又选择了1个物品1，总共选择了2个
  • 符合完全背包”每种物品可以选无限次”的要求
  • 正序遍历保证了 f[j-v[i]] 可能包含当前物品，允许继续选择

对比表格

逆序遍历 vs 正序遍历对比（以物品1，体积2，价值3为例，完全背包）：

容量j 逆序遍历（错误） 正序遍历（正确）
f[j]更新前 f[j-v[1]]
2 0 f[0]=0
3 0 f[1]=0
4 0 f[2]=0 ❌

关键区别：

  • 逆序：j=4时，f[2]还是0（未更新），只能选择1个物品1，无法实现无限次
  • 正序：j=4时，f[2]已经被更新为3，可以在已选择的基础上继续选择，实现无限次

更详细的示例（容量为6）：

容量j 正序遍历过程 说明
2 f[2] = max(0, f[0]+3) = 3 选择1个物品1
4 f[4] = max(0, f[2]+3) = max(0, 3+3) = 6 选择2个物品1（在f[2]基础上再选1个）
6 f[6] = max(0, f[4]+3) = max(0, 6+3) = 9 选择3个物品1（在f[4]基础上再选1个）

详细原理说明

状态转移方程回顾：

1
f[j] = max(f[j], f[j - v[i]] + w[i])

关键理解：

  • f[j] 表示容量为j时的最大价值
  • f[j - v[i]] 应该是可以包含当前物品i的状态
  • 在完全背包中，每个物品可以选无限次，所以 f[j - v[i]] 可以来自前i个物品的状态（包括当前物品）

正序遍历的工作原理：

  1. 从小到大遍历容量：j = v[i], v[i]+1, …, m
  2. 状态更新顺序：先更新小容量，再更新大容量
  3. 状态依赖关系：更新 f[j] 时，f[j - v[i]] 可能已经被当前物品更新过
  4. 实现无限次：f[j - v[i]] 可以包含当前物品，允许在已选择的基础上继续选择

逆序遍历的错误原因（对于完全背包）：

  1. 从大到小遍历容量：j = m, m-1, …, v[i]
  2. 状态更新顺序：先更新大容量，再更新小容量
  3. 状态依赖问题：更新 f[j] 时，f[j - v[i]] 还没有被当前物品更新过
  4. 导致错误：只能选择1次，无法实现无限次选择

代码对比

错误写法（逆序遍历，对于完全背包）：

1
2
3
4
5
6
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {  // ❌ 逆序遍历（01背包的写法）
        f[j] = max(f[j], f[j - v[i]] + w[i]);
        // f[j-v[i]]始终是前i-1个物品的状态，无法实现无限次
    }
}

正确写法（正序遍历，完全背包）：

1
2
3
4
5
6
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]);
        // f[j-v[i]]可能包含当前物品，允许继续选择
    }
}

01背包 vs 完全背包的遍历顺序对比

背包类型 遍历顺序 原因 效果
01背包 逆序（j从m到v[i]） f[j-v[i]]必须是前i-1个物品的状态 每个物品最多选1次
完全背包 正序（j从v[i]到m） f[j-v[i]]可以包含当前物品 每个物品可以选无限次

记忆技巧：

  • 01背包：逆序（倒着来，避免重复）
  • 完全背包：正序（顺着来，允许重复）

4. 01背包与完全背包的对比

特性 01背包 完全背包
物品选择 每种物品最多选1次 每种物品可以选无限次
状态转移 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]) dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])
一维DP遍历 逆序（j从m到v[i]） 正序（j从v[i]到m）
原因 避免同一物品被选多次 允许同一物品被选多次

记忆技巧：

  • 01背包：逆序（倒着来，避免重复）
  • 完全背包：正序（顺着来，允许重复）

5. 完整示例

题目：有3种物品，背包容量为5。物品信息如下：

物品 体积 价值
1 1 2
2 2 3
3 3 4

求解过程：

使用一维DP，状态转移过程：

  • i=1（物品1，体积1，价值2）：

    • j=1: f[1] = max(0, f[0]+2) = 2
    • j=2: f[2] = max(2, f[1]+2) = 4
    • j=3: f[3] = max(4, f[2]+2) = 6
    • j=4: f[4] = max(6, f[3]+2) = 8
    • j=5: f[5] = max(8, f[4]+2) = 10

  • i=2（物品2，体积2，价值3）：

    • j=2: f[2] = max(4, f[0]+3) = 4
    • j=3: f[3] = max(6, f[1]+3) = 6
    • j=4: f[4] = max(8, f[2]+3) = 8
    • j=5: f[5] = max(10, f[3]+3) = 10

  • i=3（物品3，体积3，价值4）：

    • j=3: f[3] = max(6, f[0]+4) = 6
    • j=4: f[4] = max(8, f[1]+4) = 8
    • j=5: f[5] = max(10, f[2]+4) = 10

答案：最大价值为10（选择5个物品1，或选择2个物品1和1个物品3等）

6. 时间复杂度分析

  • 时间复杂度：
    • 朴素版本：O(n×V×k)，k为每个物品最多能选择的个数
    • 优化版本：O(n×V)
  • 空间复杂度：
    • 二维DP：O(n×V)
    • 一维DP：O(V)

多重背包问题

1. 问题描述

多重背包问题：有N个物品和一个容量为V的背包。第i种物品最多有 s[i] 件可用，每件体积是 v[i]，价值是 w[i]。

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

特点：每种物品有数量限制，既不是01背包（只能选1次），也不是完全背包（可以选无限次）

2. 问题分析

方法一：常规分析方法

常规分析方法是最常用的动态规划分析方法，通过以下步骤进行：

第一步：状态定义

  • dp[i][j] 表示前i种物品，在容量为j的背包中能获得的最大价值

第二步：状态转移方程

对于第i种物品，可以选择0件、1件、2件…最多 s[i] 件。

状态转移方程：

1
2
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i], dp[i-1][j-2*v[i]] + 2*w[i], ..., dp[i-1][j-k*v[i]] + k*w[i])
其中 k = min(s[i], j/v[i])

方法二：闫氏DP分析法

闫氏DP分析法是由算法竞赛教练闫学灿（yxc）总结的一种系统化的动态规划分析方法。这种方法通过集合的角度来理解动态规划，使问题分析更加清晰和系统化。

第一步：状态表示

  • 集合：dp[i][j] 表示所有只考虑前i种物品，且总体积不超过j的选法集合
  • 属性：集合中所有方案的最大价值

第二步：状态计算

将集合 dp[i][j] 按选择第i种物品的个数k进行划分：

  • 不选第i种物品：dp[i-1][j]
  • 选1件第i种物品：dp[i-1][j-v[i]] + w[i]
  • 选2件第i种物品：dp[i-1][j-2*v[i]] + 2*w[i]
  • 选k件第i种物品：dp[i-1][j-k*v[i]] + k*w[i]（k <= s[i] 且 k*v[i] <= j）

3. 算法实现

3.1 朴素实现（三层循环）

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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];  // v[i]体积，w[i]价值，s[i]数量
int f[N][N];  // f[i][j] 表示前i种物品，容量为j时的最大价值

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i] >> s[i];
    }

    // 【状态转移】三层循环
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // 枚举选择第i种物品的个数k（0到s[i]）
            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;
    return 0;
}

代码说明：

  • 外层循环遍历物品种类
  • 中层循环遍历容量
  • 内层循环枚举选择当前物品的个数k
  • 时间复杂度：O(n×V×s)，其中s是每种物品的平均数量

为什么不能像完全背包一样省略第三重循环？

关键差别在 f[i][j-v] 的含义。

  • 完全背包：f[i][j-v] 只受容量限制，可以顺着容量不断追加当前物品，因此正序遍历也不会超限。 

    1
    2
    f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w,.., f[i-1][j-kv]+kw)
    f[i][j-v] = max(         f[i-1][j-v],   f[i-1][j-2v]+w,  f[i-1][j-3v]+2w,.., f[i-1][j-kv]+(k-1)w)

  • 多重背包：f[i][j-v] 同时受件数 S 限制，展开会额外出现“最后一项” f[i-1][j-(S+1)v] + S w，提示库存已经耗尽： 

    1
    2
    f[i,j] = max(f[i-1,j], f[i-1,j-v]+w, f[i-1,j-2v]+2w,.., f[i-1,j-sv] + sw ) 
    f[i,j-v] = max(        f[i-1,j-v],   f[i-1,j-2v]+w,.., f[i-1,j-sv]+(s-1)w, f[i-1,j-(s+1)v]+sw )

    一旦省去第三层 k 枚举，就等同默认还能继续拿，把多重背包错写成完全背包。

朴素实现里的第三层 for (int k = 0; k <= s[i] && k * v[i] <= j; k++) 是维护“已用件数”的唯一信息。想提速只能换一种表达方式（比如二进制拆分，把有限件数拆成若干个 01 物品，再按 01 背包逆序转移），既保留数量约束，又能把复杂度从 O(nVs) 降到 O(nVlog s)。

3.2 二进制优化

二进制优化是多重背包问题的重要优化方法。核心思想是：将每种物品的s[i]件物品，按照2的幂次进行分组，转化为01背包问题。

原理：任何正整数都可以表示为2的幂次之和（二进制表示），例如：

  • 7 = 1 + 2 + 4
  • 10 = 2 + 8
  • 13 = 1 + 4 + 8

这样可以将s[i]件物品拆分成 log(s[i]) 个”新物品”，每个新物品只能选一次，转化为01背包问题。

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
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 12010, M = 2010;  // N需要开大一些，因为二进制拆分后物品数量会增加

int n, m;
int v[N], w[N];  // 拆分后的物品
int f[M];  // 一维DP数组

int main() {
    cin >> n >> m;

    int cnt = 0;  // 拆分后的物品数量
    for (int i = 1; i <= n; i++) {
        int a, b, s;  // a体积，b价值，s数量
        cin >> a >> b >> s;
        
        // 【二进制拆分】
        int k = 1;
        while (k <= s) {
            cnt++;
            v[cnt] = a * k;  // 新物品的体积 = 原物品体积 × k
            w[cnt] = b * k;  // 新物品的价值 = 原物品价值 × k
            s -= k;
            k *= 2;  // 2的幂次：1, 2, 4, 8, ...
        }
        
        // 处理剩余部分
        if (s > 0) {
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;  // 更新物品数量

    // 【转化为01背包问题】
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {  // 逆序遍历（01背包）
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }

    cout << f[m] << endl;
    return 0;
}

二进制拆分示例：

假设第i种物品有7件（s[i] = 7），可以拆分为：

  • 1件（k=1）：体积v，价值w
  • 2件（k=2）：体积2v，价值2w
  • 4件（k=4）：体积4v，价值4w

这样可以用这3个”新物品”组合出0-7件原物品的所有可能。

优化效果：

  • 时间复杂度：从 O(n×V×s) 优化到 O(n×V×log(s))
  • 空间复杂度：O(V)

4. 完整示例

题目：有3种物品，背包容量为10。物品信息如下：

物品 体积 价值 数量
1 2 3 2
2 3 4 3
3 4 5 1

求解过程：

使用二进制优化后，物品拆分：

  • 物品1（2件）：拆分为 1件(2,3) 和 1件(2,3)
  • 物品2（3件）：拆分为 1件(3,4)、1件(3,4)、1件(3,4)
  • 物品3（1件）：拆分为 1件(4,5)

转化为01背包问题求解。

5. 时间复杂度分析

  • 朴素版本：O(n×V×s)
    • 需要枚举每种物品的每种数量选择
  • 二进制优化版本：O(n×V×log(s))
    • 将每种物品拆分为log(s)个新物品
    • 转化为01背包问题
  • 空间复杂度：O(V)（一维DP）

分组背包问题

1. 问题描述

分组背包问题：有N组物品和一个容量为V的背包。每组物品有若干个，同一组内的物品最多只能选一个。第i组物品中第j个物品的体积是 v[i][j]，价值是 w[i][j]。

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

特点：物品分组，每组内最多选一个，但不同组之间可以任意选择

2. 问题分析

方法一：常规分析方法

常规分析方法是最常用的动态规划分析方法，通过以下步骤进行：

第一步：状态定义

  • dp[i][j] 表示前i组物品，在容量为j的背包中能获得的最大价值

第二步：状态转移方程

对于第i组物品，有两种选择：

  1. 不选第i组的任何物品：dp[i][j] = dp[i-1][j]
  2. 选第i组的第k个物品：dp[i][j] = dp[i-1][j-v[i][k]] + w[i][k]（需要容量足够）

状态转移方程：

1
2
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i][0]] + w[i][0], dp[i-1][j-v[i][1]] + w[i][1], ..., dp[i-1][j-v[i][k]] + w[i][k])
其中k遍历第i组的所有物品

方法二：闫氏DP分析法

闫氏DP分析法是由算法竞赛教练闫学灿（yxc）总结的一种系统化的动态规划分析方法。这种方法通过集合的角度来理解动态规划，使问题分析更加清晰和系统化。

第一步：状态表示

  • 集合：dp[i][j] 表示所有只考虑前i组物品，且总体积不超过j的选法集合
  • 属性：集合中所有方案的最大价值

第二步：状态计算

将集合 dp[i][j] 按是否选择第i组物品进行划分：

  1. 不选第i组的任何物品：dp[i-1][j]
  2. 选第i组的第0个物品：dp[i-1][j-v[i][0]] + w[i][0]
  3. 选第i组的第1个物品：dp[i-1][j-v[i][1]] + w[i][1]
  4. 选第i组的第k个物品：dp[i-1][j-v[i][k]] + w[i][k]

3. 算法实现

3.1 二维DP实现

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
#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int f[N][N];  // f[i][j] 表示前i组物品，容量为j时的最大价值
int v[N][N], w[N][N], s[N];  // v[i][j]第i组第j个物品的体积，w[i][j]价值，s[i]第i组物品个数
int n, m;

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        cin >> s[i];  // 第i组物品的个数
        for (int j = 0; j < s[i]; j++) {
            cin >> v[i][j] >> w[i][j];  // 读入第i组第j个物品的体积和价值
        }
    }

    // 【状态转移】
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // 不选第i组的任何物品
            f[i][j] = f[i - 1][j];
            
            // 遍历第i组的所有物品，选择其中一个
            for (int k = 0; k < s[i]; k++) {
                if (j >= v[i][k]) {
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
                }
            }
        }
    }
    
    cout << f[n][m] << endl;
    return 0;
}

代码说明：

  • 外层循环遍历组
  • 中层循环遍历容量
  • 内层循环遍历当前组内的所有物品
  • 对于每组，最多只能选择一个物品

3.2 一维DP优化（空间优化）

分组背包也可以使用一维数组优化，但需要注意：容量需要逆序遍历，因为每组内最多只能选一个物品，类似于01背包。

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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];  // v[i][j]第i组第j个物品的体积，w[i][j]价值，s[i]第i组物品个数
int f[N];  // 一维DP数组

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 0; j < s[i]; j++) {
            cin >> v[i][j] >> w[i][j];
        }
    }

    // 【状态转移】一维优化
    for (int i = 1; i <= n; i++) {
        // 【关键】逆序遍历容量，保证每组最多选一个（类似01背包）
        for (int j = m; j >= 0; j--) {
            // 遍历第i组的所有物品
            for (int k = 0; k < s[i]; k++) {
                if (v[i][k] <= j) {
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }

    cout << f[m] << endl;
    return 0;
}

为什么需要逆序遍历？

这是分组背包一维优化的关键点，与01背包类似，但需要特别注意循环顺序！

正序遍历的问题

如果使用正序遍历（j从0到m），会发生什么？

示例：有1组物品（第1组），包含2个物品：

  • 物品1-0：体积v[1][0]=2，价值w[1][0]=3
  • 物品1-1：体积v[1][1]=3，价值w[1][1]=4

背包容量m=5

正序遍历过程（错误示例，对于分组背包）：

假设当前处理第1组，正序遍历容量j：

步骤 j 处理物品 f[j] 更新前 f[j-v[1][k]] f[j] 更新后 说明
1 2 物品1-0 f[2]=0 f[0]=0 f[2]=max(0, 0+3)=3 ✅ 正确：选择物品1-0
2 3 物品1-0 f[3]=0 f[1]=0 f[3]=max(0, 0+3)=3 ✅ 正确：选择物品1-0
3 3 物品1-1 f[3]=3 f[0]=0 f[3]=max(3, 0+4)=4 ✅ 正确：选择物品1-1
4 4 物品1-0 f[4]=0 f[2]=3 f[4]=max(0, 3+3)=6 ❌ 错误：选择了2个物品1-0！
5 5 物品1-0 f[5]=0 f[3]=4 f[5]=max(0, 4+3)=7 ❌ 错误：选择了物品1-1和物品1-0！

问题分析：

  • 当j=4时，处理物品1-0，f[2]已经被更新为3（表示已经选择了物品1-0）
  • f[4] = max(f[4], f[2] + w[1][0]) = max(0, 3+3) = 6
  • 这表示在已经选择物品1-0的基础上，又选择了物品1-0，违反了”每组最多选一个物品”的规则
  • 当j=5时，处理物品1-0，f[3]已经被更新为4（表示已经选择了物品1-1）
  • f[5] = max(f[5], f[3] + w[1][0]) = max(0, 4+3) = 7
  • 这表示选择了物品1-1和物品1-0，同样违反了规则

逆序遍历的正确性

使用逆序遍历（j从m到0），可以确保每组最多只选一个物品。

逆序遍历过程（正确示例）：

步骤 j 处理物品 f[j] 更新前 f[j-v[1][k]] f[j] 更新后 说明
1 5 物品1-0 f[5]=0 f[3]=0 f[5]=max(0, 0+3)=3 ✅ 正确：选择物品1-0
2 5 物品1-1 f[5]=3 f[2]=0 f[5]=max(3, 0+4)=4 ✅ 正确：选择物品1-1（更优）
3 4 物品1-0 f[4]=0 f[2]=0 f[4]=max(0, 0+3)=3 ✅ 正确：选择物品1-0
4 4 物品1-1 f[4]=3 f[1]=0 f[4]=max(3, 0+4)=4 ✅ 正确：选择物品1-1（更优）
5 3 物品1-0 f[3]=0 f[1]=0 f[3]=max(0, 0+3)=3 ✅ 正确：选择物品1-0
6 3 物品1-1 f[3]=3 f[0]=0 f[3]=max(3, 0+4)=4 ✅ 正确：选择物品1-1（更优）
7 2 物品1-0 f[2]=0 f[0]=0 f[2]=max(0, 0+3)=3 ✅ 正确：选择物品1-0

正确性分析：

  • 当j=5时，处理物品1-0，f[3]还是0（未被当前组更新），使用的是前0组的状态
  • f[5] = max(f[5], f[3] + w[1][0]) = max(0, 0+3) = 3
  • 然后处理物品1-1，f[2]还是0，f[5] = max(3, 0+4) = 4
  • 最终f[5]=4，只选择了物品1-1，符合”每组最多选一个”的规则
  • 逆序遍历保证了在处理第i组的物品时，f[j-v[i][k]]使用的是前i-1组的状态

对比表格

正序遍历 vs 逆序遍历对比（以第1组，2个物品为例，分组背包）：

第1组物品：

  • 物品1-0：体积2，价值3
  • 物品1-1：体积3，价值4
容量j 正序遍历（错误） 逆序遍历（正确）
处理过程 f[j]最终值
2 物品1-0: f[2]=max(0, f[0]+3)=3 3 ✅
3 物品1-0: f[3]=max(0, f[1]+3)=3
物品1-1: f[3]=max(3, f[0]+4)=4		 4 ✅
4 物品1-0: f[4]=max(0, f[2]+3)=6 ❌ 6 ❌
5 物品1-0: f[5]=max(0, f[3]+3)=7 ❌ 7 ❌

关键区别：

  • 正序：j=4时，f[2]已经被更新为3（已选物品1-0），导致可以再选物品1-0，违反规则
  • 逆序：j=4时，f[2]还是0（未更新），使用的是前0组的状态，确保每组最多选一个

错误示例详细说明（正序遍历，j=4）：

  • 处理物品1-0：f[4] = max(0, f[2]+3) = max(0, 3+3) = 6
  • 此时f[2]=3表示已经选择了物品1-0，再选物品1-0就违反了”每组最多选一个”的规则
  • 正确结果应该是4（选择物品1-1，价值更高）

详细原理说明

状态转移方程回顾：

1
f[j] = max(f[j], f[j - v[i][k]] + w[i][k])

关键理解：

  • f[j] 表示容量为j时的最大价值
  • f[j - v[i][k]] 应该是前i-1组的状态，不能包含当前组的任何物品
  • 在分组背包中，每组最多只能选一个物品，所以 f[j - v[i][k]] 必须来自前i-1组的状态

逆序遍历的工作原理：

  1. 从大到小遍历容量：j = m, m-1, …, 0
  2. 状态更新顺序：先更新大容量，再更新小容量
  3. 状态依赖关系：更新 f[j] 时，f[j - v[i][k]] 还没有被当前组的物品更新过
  4. 确保每组最多选一个：f[j - v[i][k]] 来自前i-1组，保证当前组最多只选一个物品

正序遍历的错误原因（对于分组背包）：

  1. 从小到大遍历容量：j = 0, 1, …, m
  2. 状态更新顺序：先更新小容量，再更新大容量
  3. 状态依赖问题：更新 f[j] 时，f[j - v[i][k]] 可能已经被当前组的其他物品更新过
  4. 导致错误：可能在同一组内选择多个物品，违反”每组最多选一个”的规则

循环顺序的重要性：

分组背包一维优化的正确循环顺序：

1
2
3
4
5
6
7
8
9
for (int i = 1; i <= n; i++) {           // 外层：遍历组
    for (int j = m; j >= 0; j--) {        // 中层：逆序遍历容量
        for (int k = 0; k < s[i]; k++) {  // 内层：遍历组内物品
            if (v[i][k] <= j) {
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
        }
    }
}

为什么内层循环在容量循环内部？

  • 如果内层循环在容量循环外部，会导致同一组内的物品在不同容量下重复选择
  • 将内层循环放在容量循环内部，确保对于每个容量j，只从当前组中选择一个最优物品

代码对比

错误写法（正序遍历，对于分组背包）：

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {  // ❌ 正序遍历
        for (int k = 0; k < s[i]; k++) {
            if (v[i][k] <= j) {
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                // f[j-v[i][k]]可能已被当前组的其他物品更新，导致同一组选多个
            }
        }
    }
}

错误写法（内层循环位置错误）：

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i++) {
    for (int k = 0; k < s[i]; k++) {  // ❌ 内层循环在外层
        for (int j = m; j >= v[i][k]; j--) {
            f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            // 这样会导致同一组内的物品在不同容量下重复选择
        }
    }
}

正确写法（逆序遍历，分组背包）：

1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 0; j--) {  // ✅ 逆序遍历容量
        for (int k = 0; k < s[i]; k++) {  // ✅ 内层循环在容量循环内部
            if (v[i][k] <= j) {
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                // f[j-v[i][k]]来自前i-1组，确保每组最多选一个
            }
        }
    }
}

分组背包 vs 01背包的遍历顺序对比

背包类型 遍历顺序 原因 效果
01背包 逆序（j从m到v[i]） f[j-v[i]]必须是前i-1个物品的状态 每个物品最多选1次
分组背包 逆序（j从m到0） f[j-v[i][k]]必须是前i-1组的状态 每组最多选1个物品

相同点：

  • 都使用逆序遍历
  • 都是为了确保”最多选一次”的限制

不同点：

  • 01背包：每个物品独立，逆序保证每个物品最多选1次
  • 分组背包：每组内多个物品，逆序+内层循环保证每组最多选1个物品

记忆技巧：

  • 01背包：逆序（倒着来，避免重复）
  • 分组背包：逆序+内层循环（倒着来，每组选一个）

循环顺序说明：

  • 外层：遍历组（i从1到n）
  • 中层：逆序遍历容量（j从m到0）
  • 内层：遍历当前组内的物品（k从0到s[i]-1）

4. 完整示例

题目：有3组物品，背包容量为10。物品信息如下：

第1组（2个物品）：

  • 物品1-1：体积2，价值3
  • 物品1-2：体积3，价值4

第2组（2个物品）：

  • 物品2-1：体积4，价值5
  • 物品2-2：体积5，价值6

第3组（1个物品）：

  • 物品3-1：体积3，价值4

求解思路：

  • 每组最多选一个物品
  • 可以选第1组的物品1-1，第2组的物品2-1，第3组的物品3-1
  • 总价值 = 3 + 5 + 4 = 12

5. 时间复杂度分析

  • 时间复杂度：O(n×V×s)
    • n个组，每组最多s个物品，容量V
    • 需要遍历所有组、所有容量、每组内所有物品
  • 空间复杂度：
    • 二维DP：O(n×V)
    • 一维DP：O(V)

四种背包问题的对比

背包类型 物品选择限制 状态转移 一维DP遍历 时间复杂度
01背包 每种物品最多选1次 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]) 逆序 O(n×V)
完全背包 每种物品可以选无限次 dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i]) 正序 O(n×V)
多重背包 每种物品最多选s[i]次 三层循环或二进制优化 逆序（优化后） O(n×V×s) 或 O(n×V×log(s))
分组背包 每组最多选1个物品 遍历组内所有物品 逆序 O(n×V×s)

记忆技巧：

  • 逆序：01背包、多重背包（优化后）、分组背包
  • 正序：完全背包

总结

01背包和完全背包的核心区别

  1. 物品选择限制：

    • 01背包：每种物品最多选1次
    • 完全背包：每种物品可以选无限次

  2. 状态转移方程：

    • 01背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
    • 完全背包：dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])

  3. 一维DP遍历顺序：

    • 01背包：逆序遍历（j从m到v[i]）
    • 完全背包：正序遍历（j从v[i]到m）

  4. 理解要点：

    • 01背包的 dp[i-1][j-v[i]] 表示”前i-1个物品”的状态，保证当前物品只选一次
    • 完全背包的 dp[i][j-v[i]] 表示”前i个物品”的状态，允许当前物品继续选择

Q&A