数据结构与算法学习笔记----背包问题

数据结构与算法学习 笔记----背包问题

@@ author: 明月清了个风
@@ first publish time: 2025.2.7

ps⭐️讲解了几种经典的背包问题：01背包，完全背包，多重背包及其变形，分组背包，讲解了他们的异同及对应的代码和优化方式，本讲中因为有代码上的优化过程，因此代码模块不单独列出，都直接在优化的过程中给出了。

Acwing 2. 01背包问题

[原题链接](2. 01背包问题 - AcWing题库)

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ 。

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

输入格式

第一行包含两个整数， $N ， V$ ，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i,w_i$ ，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$\le N,V \le 1000$ ,

$\le v_i,w_i \le 1000$

思路

背包问题是一类经典的动态规划问题， $01$ 背包也是所有背包问题中最简单的，我们直接介绍基础做法。

这题其实可以使用暴力搜索的方法，遍历所有的方案，也就是每个物品选或不选，并判断体积是否满足条件。但是总的方案数就成了 $2^n$ ， $n$ 表示物品的数量，肯定会超时，而动态规划的方法可以时间复杂度降到很低。

对于动态规划而言，我们需要确定状态的表示方法以及转移方程。

背包问题其实是一个选择组合问题，对于选择组合问题而言，我们的状态表示方法其实都很类似。本题中，使用f[i][j]表示只看前i个物品，总体积是j的情况下的最大总价值，那么我们最终要求的就是f[N][V]。

对于状态计算转移而言，需要将当前状态划分为不同的子状态进行转移，f[i][j]所表示的方案可以分为两种情况：是否包含了第i个物品。这样的划分方法做到了不重不漏，这通常是动态规划问题中的一个关键点（当然有些问题也会有特例）

不选第i个物品，那么f[i][j] = f[i - 1][j];
选第i个物品，那么f[i][j] = 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[0][0] = 0即可，代表的意思就是只看前0个物品，总体积是0的情况下的最大总价值是0，很容易理解，下面给出了这样做法的代码：

#include <iostream>
#include <cstdio>using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[N][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 = 0; j <= m; j ++){f[i][j] = f[i - 1][j];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] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])，对于第一维i而言，第i层的状态只会用到上一层i - 1层的数值，因此考虑使用滚动数组进行优化，也就是每次只需要保留一层的结果即可。

同时我们观察第二维，每次状态转移只使用到了j和j - v[i]，也就是用小数j - v[i]更新了大数j，这意味着我们需要倒序遍历，因为如果正序遍历的话，我们会先更新小数，后更新大数，而更新意味着第一维i层数的变化，原来i - 1层的数已经被更新为了i层，再去更新大数时用的就不是上一层记录的数值了，下面我们给出优化过后的代码

#include <iostream>
#include <cstdio>using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[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] = max(f[j], f[j - v[i]] + w[i]);}}cout << f[m] << endl;return 0;
}

Acwing 2. 完全背包问题

[原题链接](3. 完全背包问题 - AcWing题库)

有 $N$ 件物品和一个容量是 $V$ 的背包。每种物品都有无限件可用。

第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ 。

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

输入格式

第一行包含两个整数， $N ， V$ ，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i,w_i$ ，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$\le N,V \le 1000$ ,

$\le v_i,w_i \le 1000$

思路

完全背包问题同样可以用01背包的思路解决，考虑其状态表示及状态转移方法

对于状态表示来说，和01背包完全一样，f[i][j]表示了所有只考虑前i个物品，且总体积不超过j的所有选法的最大值。

对于状态转移来说，同样考虑对第i个物品进行划分，因为完全背包问题中每个物品可以挑选无穷多件，因此所有的方案可以分为挑选 $\; (k = 0,1,2,\cdots)$ 个第 $i$ 件物品，这样可以保证包含了所有的方案，然后就可以通过每个子集的状态计算f[i][j]了

挑选0件第i个物品，不选第i个物品，那就是只考虑前i - 1个物品，因此状态为f[i - 1][j].
挑选1件第i个物品，那么可以将状态f[i][j]中的第i个物品去掉得到之前的状态，也就是f[i - 1][j - v[i]] + w[i]，因为去掉第i个物品后就是只考虑前i - 1个物品了，而且我们选择了1件，因此也要为其留出空间，也就是j - v[i].
挑选2件第i个物品，和上面相同，可以将其去掉，也就是f[i - 1][j - 2 * v[i]] + 2 * w[i]

依次类推，我们就可以得到k件的状态f[i - 1][j - k * v[i]] + k * w[i]，体现在代码中就是一个循环，并且要判断维度j - k * v[i]的合法性，也就是if(j > k * v[i])。

由此我们可以得到下面的代码

#include <iostream>
#include <cstdio>using namespace std;const int N = 1010;int n, m;
int f[N][N];
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 = 0; j <= m; j ++)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;
}

在01背包问题中，我们使用滚动数组优化了空间，在这里，我们可以同样可以尝试。

首先我们给出f[i][j]实际是哪些状态计算得来的：

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

再来看另一个状态f[i][j - v]：

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

上下两种状态对比可以发现，f[i][j - v]的表达式加上w就是f[i][j]中包含的状态，因此状态转移方程可以优化成f[i][j] = max(f[i - 1][j], f[i][j - v] + w)。也就是将上面计算中的 $k$ 种状态中的最大值，优化成了只有两种状态的最大值，下面是优化的代码

#include <iostream>
#include <cstdio>using namespace std;const int N = 1010;int n, m;
int f[N][N];
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 = 0; j <= m; j ++){f[i][j] = f[i - 1][j];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;
}

由此我们又可以进一步进行优化，观察新的状态转移方程可以发现，每次都只会用到第i层的数据进行更新，同样使用滚动数组的方式，同时，在01背包时我们是倒序遍历，因为要使用上一层的数据，但是在这里发现，我们使用的是同一层的j - v[i]的数据，因此正常遍历即可，代码如下

#include <iostream>
#include <cstdio>using namespace std;const int N = 1010;int n, m;
int f[N];
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 = v[i]; j <= m; j ++){f[j] = max(f[j], f[j - v[i]] + w[i]);}}cout << f[m] << endl;return 0;
}

Acwing 4. 多重背包问题 I

[原题链接](4. 多重背包问题 I - AcWing题库)

有 $N$ 件物品和一个容量是 $V$ 的背包。

第 $i$ 件物品最多有 $s_i$ 件，每件体积是 $v_i$ ，价值是 $w_i$ 。

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

输入格式

第一行包含两个整数， $N ， V$ ，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i,w_i,s_i$ ，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$\le N,V \le 100$ ,

$\le v_i,w_i,s_i \le 100$

思路

和上面两题一样，只是又多了一个限制条件——每件物品的数量是有限的，因此同样使用上面的思路。

对于状态表示f[i][j]表示所有从前i个物品中选，并且总体积不超过j的选法中价值最大的。

对于状态转移，同样根据第i个物品的选择情况——可以分为选 $0,1,\cdots,s_i$ 个，因此状态转移方程和完全背包问题完全一样:

f[i][j] = max(f[i - 1][j - k * v[i]] + k * w[i]) (k = 0,1,2,..., s[i])

由此，我们可以给出以下代码：

#include <iostream>
#include <cstdio>using namespace std;const int N = 110;int n, m;
int f[N][N];
int v[N], w[N], s[N];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 ++)for(int k = 0; k <= s[i] && 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;
}

同样的，观察状态转移方程可以发现，每次更新使用的都是i - 1层的结果，因此可以使用滚动数组优化，降低空间复杂度，这里需要注意的是对于体积j需要进行倒序遍历，理由和01背包中一样，到这如果忘了去上面复习。

#include <iostream>
#include <cstdio>using namespace std;const int N = 110;int n, m;
int f[N];
int v[N], w[N], s[N];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 = 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;return 0;
}

这里会出现一个问题，是否还可以像完全背包那样优化状态转移方程，也就是将三重循环优化到两重循环。

答案是不可以。对于完全背包中的优化，我们是通过对比了两个状态的表达式得到的，可以优化的前提是两个表达式内容完全相同，但是在这一题中并不一定，因为我们的数量是有限制的，这就导致两个表达式的项数其实可能会不一样，我们可以来对比一样f[i][j]和f[i][j - v[i]]的表达式，下面就把完全背包中的两个表达式列出
$f_{i,j} = max(f_{i - 1,j},\;f_{i - 1,j - v} + w,\;f_{i - 1,j - 2v} + 2w, \cdots, f_{i - 1,j - kv} + kw) \\ f_{i,j - v} = max(f_{i - 1,j - v},\; f_{i - 1,j - 2v} + w,\; \cdots, f_{i - 1,j - kv} + (k - 1)w) \\$
在这一题中，看似第二个表达式加上 $w$ 就是第一个表达式的后面部分，但是要考虑到一个情况，就是** $f_{i,j - v}$ 的体积j - v仍能装下所有的 $k$ 个物品**。

换一种说法可能会更好理解，第二个表达式 $f_{i,j - v}$ 中的 $j - v$ 的中的 $v$ 并不是为一个第 $i$ 件物品预留的，而在第一个表达式中的所有涉及到 $- v$ 的项，这些体积 $v,2v,3v,\cdots,kv$ ，这些的含义都是为 $k$ 个第 $i$ 件物品预留位置。因此，第二个表达式虽然预先减去了一个体积 $v$ ，但是他最后可能还多一项 $f_{i,j - v - kv} + kw$ ，因为体积 $j - v$ 仍可能装下所有的 $k$ 件第 $i$ 个物品，而这多的一项是不可能出现在第一个表达式中的。

Acwing 5. 多重背包问题 II

[原题链接](5. 多重背包问题 II - AcWing题库)

有 $N$ 件物品和一个容量是 $V$ 的背包。

第 $i$ 件物品最多有 $s_i$ 件，每件体积是 $v_i$ ，价值是 $w_i$ 。

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

输入格式

第一行包含两个整数， $N ， V$ ，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i,w_i,s_i$ ，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$\le N \le 1000$ ,

$\le V \le 2000$

$\le v_i,w_i,s_i \le 2000$

思路

这一题也是多重背包，但是相对于上一题来说，数据范围发生了很大的变化，观察上一题的代码可以发现主要代码是三重循环，如果用到这一题来的话就是 $40$ 亿，一定超时，因此需要进行优化。

这里我们用到的优化方式是二进制优化，其实这个思路我们之前已经学过了，在快速幂中，如果没有学过或者忘了，可以先去看一下，是非常类似的思想。我们可以在 $\log n$ 的复杂度上枚举 $n$ 级别的数，下面我们来看具体怎么优化。

先举个例子，假设我们有 $200$ 个物品，那么我们可能的拿取方式就是 $0,1,2，\cdots，200$ 个物品，也就是 $201$ 种取法，需要枚举 $201$ 次，但是如果我们通过二进制打包，也就是将物品看成 $0,1,2,4，\cdots,64$ 个物品，我们就能通过这些打包过的凑出 $\sim 127$ 的所有数，这时将最后一份打包成 $73$ 个，那么就能凑出 $\sim 200$ 的所有数。

为啥能凑出这些数，我们用更小的范围举例，如用 $0, 1, 2$ ，我们就能凑出 $\sim 3$ ，那么加上一个 $2^2 = 4$ ，我们就能凑出 $\sim 7$ ，同理继续向上累加即可，我们用 $2^1, 2^2, \cdots, 2^k$ 可以凑出 $\sim 2^k - 1$ 中的所有数，那么假设我们要凑的是 $s$ ，我们需要的就是 $2^1, 2^2, \cdots, 2^k$ ，其中 $2^k$ 应满足 $2^1 + 2^2 + \cdots + 2^k < s$ 并且 $2^1 + 2^2 + \cdots + 2^k + 2^{k + 1} > s$ 。

此时我们需要用到的所有数就是 $2^1, 2^2, \cdots, 2^k, s - (2^1 + 2^2 + \cdots + 2^k)$ ，

我们将每个物品都这样处理后，将可以将多重背包问题转化为 $01$ 背包问题，对于打包过后的每个物品的数量拿与不拿的方案等价于打包前拿多少个每个物品的方案，下面就看代码吧，这里直接使用了 $01$ 背包问题滚动数组优化过的代码：

#include <iostream>
#include <cstdio>using namespace std;const int N = 25000, M = 2010;int n, m;
int v[N], w[N];
int f[M];int main()
{cin >> n >> m;int cnt = 0;  // 记录转化后一共有多少个物品。for(int i = 0; i < n; i ++){int a, b, s;cin >> a >> b >> s;int k = 1;  // 对于每个物品都进行二进制优化，每份打包为2^k个while(k <= s){cnt ++;v[cnt] = a * k;w[cnt] = b * k;s -= k;k *= 2;}if(s > 0)  // 最后剩下的打包在一起{cnt ++;v[cnt] = a * s;w[cnt] = b * s;}}for(int i = 1; i <= cnt; 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;
}

Acwing \9. 分组背包问题

[原题链接](9. 分组背包问题 - AcWing题库)

有 $N$ 组物品和一个容量是 $V$ 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。

每件物品体积是 $v_ij$ ，价值是 $w_ij$ ，其中 $i$ 是组号， $j$ 是组内编号。

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

输入格式

第一行包含两个整数， $N ， V$ ，用空格隔开，分别表示物品组数和背包容积。

接下来有 $N$ 组数据

每组数据第一行有一个整数 $s_i$ ，表示第 $i$ 个物品组的物品数量；
每组数据接下来有 $s_i$ 行，每行有两个整数 $v_{ij},w_{ij}$ ，用空格隔开，分别表示第 $i$ 个物品组的第 $j$ 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

$\le N，V \le 100$ ,

$\le s_i \le 100$

$\le v_{ij} ,w_{ij} \le 100$

思路

同样的，考虑状态表示和状态计算方法

对于状态表示，我们使用f[i][j]表示只从前 $i$ 组物品中选，且总体积不大于 $j$ 的所有选法集合的最大值；

对于状态计算，我们同样根据第 $i$ 组物品的选择情况进行分类，可将f[i][j]分别第 $i$ 组物品中选择 $0$ 个物品，选择第 $1,2,\cdots,s_i ）$ 个物品，这题相对比较简单，因为前面已经讲过很多遍了。

#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;using namespace std;const int N = 110;int n, m;
int v[N][N], w[N][N];
int s[N];
int f[N];int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++){cin >> s[i];for(int j = 1; j <= s[i]; j ++)cin >> v[i][j] >> w[i][j];}for(int i = 1; i <= n; i ++){for(int j = m; j >= 0; j --)for(int k = 0; k <= s[i]; k ++)if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);}cout << f[m] << endl;return 0;
}