乐东黎族自治县网站建设_网站建设公司_阿里云_seo优化

概述

本文以01背包问题为基础，逐步扩展到到完全背包，多重背包，混合背包，二维费用背包，分组背包，有依赖的背包（树上背包），背包求方案数和具体方案这9种基本的背包问题，并给出尽可能精简的代码模版（C++），同时会介绍它们各个问题的的时间、空间优化，并给出具体的题目测试连接，方便自行检验。

引言

问题背景

背包问题是运筹学领域经典的组合优化问题，核心目标是在给定资源约束（如背包容量）下，从一组物品中选择一个子集，使得选中物品的总价值最大化（或总消耗最小化），同时满足资源约束条件。

前置要求

1. 本文章的所有问题的代码均以C++语言实现，当并没有运用一些高级的C++语法，只需具备一定的C基础即可。

2. 阅读本文章需要对DP的一些基本概念，如最优子结构、重叠子问题、阶段、状态、决策、状态转移方程等均有一定了解。

3. 由于树上背包需要建图，所以要求读者至少会一种建图的方法，可以是邻接表、邻接矩阵、链式前向星等任意一种即可。

01背包问题

题目概述

给定\(n\)个物品和一个容量为\(m\)的背包，以及第\(i\)个物品体积\(v_i\)，价值\(w_i\)，每个物品只有一个，求总容量不超过\(m\)的选择方案的最大价值。

• 测试连接：2. 01背包问题

暴力枚举子集

由于每个物体只有两种可能的状态（取与不取），那么对于\(n\)个物品，我们可以用\(2^n\)表示所有可能的状态。不妨用0表示不取，1表示取，代码如下所示。

实现

#include <iostream>
using namespace std;
const int N = 1010;
int n, m, w[N], v[N];
int ans;int main() {cin >> n >> m;for (int i = 0; i < n; i ++) cin >> v[i] >> w[i];for (int i = 0; i < 1 << n; i ++) {int x = 0, y = 0;for (int j = 0; j < n; j ++) {if (i & (1 << j)) {x += v[j];y += w[j];}}if (x <= m && y > ans) ans = y;}cout << ans;return 0;
}  

该枚举方式的时间复杂度是\(O(2^n)\)，当\(n=25\)时，\(2^n>10^7\)，显然无法在合理时间内完成计算。

动态规划优化思路

假设按照物品编号从左到右依次进行决策。显然，对于第\(n\)个物品的决策（取或不取）的最大价值需依赖于前\(n-1\)个物品的决策在特定容量约束下的决策。以此类推，我们可以将该问题划分为\(n\)阶段的线性决策。

要使得在对第\(n\)个物品进行决策后整体的价值最大，考虑第\(n\)个物品的两种决策方式：

• 不取第\(n\)件物品，此时需要知道前\(n-1\)件物品在容量约束为\(m\)下决策后的最大价值。
• 取第\(n\)件物品，假设第\(n\)件物的体积为\(v\)，那么我们需要知道前\(n-1\)件物品在容量约束为\(m-v\)决策后的最大价值。

由于\(m-v\)可能是\([0,m]\)的任意值，于是我们需要求出阶段\(n-1\)所有容量下的最大价值。

按照考虑第阶段\(n\)的方式，可以依次考虑阶段\(n-1,n-2,...,1\)，不难发现，它们是相同且规模更小的问题。且从\(1\)开始，可以逐步由局部最优推广到全局最优。于是我们定义状态\(f_{i,j}\)表示考虑前\(i\)个物品且总容量不超过\(j\)的最大价值：

• 不选第\(i\)个物品：\(f_{i,j}=f_{i-1,j}\)
• 选第\(i\)个物品：\(f_{i,j}=f_{i-1,j-v_i}+w_i, \ j\ge v_i\)

阶段\(1\)为初始阶段，需要我们手动定义，但不难注意到，当初始条件满足：\(f_{0,j}=0, \ \forall j\in [0,m]\)，可以省略该阶段的定义。

综合得到状态转移方程

\[f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i\} \]

滚动数组优化

仔细观察上述状态转移方程，不难看出，对于当前阶段状态\(f_{i,j}\)仅仅依赖于前一个阶段阶段的状态\(f_{i-1,j}\)和\(f_{i-1,j-v_i}\)，于是我们想是否可以仅仅通过保留前一个阶段的状态，计算当前阶段的最大价值。不难发现，如果从小到大枚举\(j\)，在计算当前阶段状态时会出现覆盖前一个阶段的状态的情况，于是我们可以考虑从大到小枚举，于是可以压缩阶段的状态为

\[f_j=\max\{f_j,f_{j-v_i}+w_i\} \]

代码实现

#include <iostream>
using namespace std;
constexpr int N = 1010;
int f[N];int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i ++) {int v, w;cin >> v >> w;for (int j = m; j >= v; j --) {f[j] = max(f[j], f[j - v] + w);}}cout << f[m];return 0;
} 

对于二维状态，留给读者自行实现，这里不做过多赘述。

复杂度分析

• 时间复杂度：\(O(nm)\)。
• 空间复杂度：\(O(m)\)，不考虑输入。

完全背包

题目概述

给定\(n\)个物品和一个容量为\(m\)的背包，以及第\(i\)个物品的体积\(v_i\)、价值\(w_i\)，且每个物品可以被选择无限次，求在总容量不超过\(m\)的前提下可获得的最大价值。

• 测试连接：3. 完全背包问题

思路

沿用01背包的分析方式，定义\(f_{i,j}\)表示考虑前\(i\)个物品、且总容量不超过\(j\)时的最大价值。由于完全背包中的每个物品可以取无限次，可以增加一层循环，枚举满足\(kv_i\le j\)的取用次数\(k\)。但该方法的时间复杂度为\(O(n^2m)\)，显然无法接受，因此需要进行优化。

将\(f_{i,j}\)所有可能的依赖状态展开，有

\[f_{i,j} = \max_{k=0}^{k\times v_i\le j} \big( f_{i-1,j}, f_{i-1,j-v_i}+w_i, f_{i-1,j-2v_i}+2w_i, \dots, f_{i-1,j-kv_i}+kw_i \big) \]

容易观察到，在排除\(k=0\)的情况后，其余状态可以统一表示为\(f_{i,j-v_i}+w_i\)。同时，当\(j\)从小到大枚举时，在计算\(f_{i,j}\)时，\(f_{i,j-v_i}\)已经被计算完成，因此状态转移方程可以简化为

\[f_{i,j}=\max(f_{i-1,j},f_{i,j-v_i}+w_i) \]

进一步可以发现，对于当前阶段的状态\(f_{i,j}\)，其仅依赖于前一阶段的状态\(f_{i-1,j}\)以及当前阶段的状态\(f_{i,j-v_i}\)。因此，当\(j\)从小到大枚举时，可以进行状态压缩，得到

\[f_j=\max(f_j,f_{j-v_i}+w_i) \]

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i ++) {int v, w;for (int j = v; j <= m; j ++) {f[j] = max(f[j], f[j - v] + w);}}cout << f[m];return 0;
}

复杂度分析

• 时间复杂度：\(O(nm)\)。
• 空间复杂度：\(O(m)\)。

多重背包

题目概述

给定\(n\)个物品和一个容量为\(m\)的背包，以及第\(i\)个物品的体积\(v_i\)、价值\(w_i\)和物品数量\(s_i\)，求在总容量不超过\(m\)的前提下可获得的最大价值。

• 二进制化测试连接：5. 多重背包问题 II
• 单调队列优化测试连接：6. 多重背包问题 III

思路

同样基于01背包的分析方式，定义\(f_{i,j}\)表示考虑前\(i\)个物品、且总容量不超过\(j\)时的最大价值。由于第\(i\)个物品最多可以选取\(s_i\)个，可以在转移时额外增加一层循环枚举选取数量不超过\(s_i\)的情况，其时间复杂度为\(O(nms)\)，其中\(s=\max\{s_1,\dots,s_n\}\)。当\(n,m,s\)同阶时，该复杂度通常无法接受，因此需要进一步优化。

需要注意的是，完全背包的优化方式不能直接应用于多重背包。这是因为完全背包允许无限取用某一物品，其状态转移所依赖的范围严格大于多重背包。下面通过一个简单例子说明这一差异：

• 考虑\(n=1,m=9,v_1=3,w_1=5,c_1=2\)，可以发现，若为完全背包，最大价值为15；而在多重背包中，最大价值仅为10。

换句话说，多重背包在将第\(i\)件物品全部选取完后，可能仍存在无法继续装入该物品的剩余容量，从而导致其性质与完全背包本质不同。

二进制优化

引理（二进制拆分原理）

若\(S=2^0+2^1+\dots+2^{k-1},k\in N^{+}\)，则集合\(\{2^0,2^1,\dots,2^{k-1}\}\)的元素可以通过加法组合表示区间\([0,S]\)内的所有整数。

可通过数学归纳法证明，留给读者自行完成。

推论

进一步证明：若\(S=2^0+2^1+\dots+2^{k-1}+x,1\le x<2^{k}\)，则集合\(\{2^0,2^1,\dots,2^{k-1},x\}\)可以组合出\([0,S]\)内的所有整数。

设集合\(Q=\{2^0,2^1,\dots,2^{k-1}\}\)，并令\(S'=2^0+2^1+\dots+2^{k-1}\)。由上述引理可知，区间\([0,S']\)可以由集合\(Q\)表示。于是只需证明区间\([S',S]\)可以由集合\(P=Q\cup\{x\}\)表示。

对于任意\(S'+n,1\le n\le x,n\in N^{+}\)，有

\[S'+n=(S'+n-x)+x \]

又因为\(n\le x\Rightarrow S'+n-x\le S'\)，所以\(S'+n-x\)可由\(Q\)表示，从而\(S'+n\)可由\(P\)表示。当\(n=x\)时，\(S'+x\)同样可由\(P\)表示，故命题成立。

思路

对于第\(i\)个物品的数量\(s_i\)，若可以将其拆分为若干份，使这些份数的组合能够表示区间\([0,s_i]\)内的任意整数，则原多重背包问题可等价转化为01背包问题。

具体而言，将\(s_i\)按2的整数幂进行拆分。设\(k\)为满足\(s_i\ge2^0+2^1+\dots+2^{k-1}\)的最大整数，分类讨论\(s_i\)的两种情况：

• 若\(s_i=2^0+2^1+\dots+2^{k-1}\)，由上述引理，可直接转换为01背包问题。
• 若\(s_i=2^0+2^1+\dots+2^{k-1}+x,1\le x<2^{k}\)，由上述推论，同样可以转换为01背包问题。

通过上述分析，多重背包问题可以通过二进制拆分完全转化为01背包问题，下面给出若干示例以帮助理解拆分过程：

• \(6=1+2+3\)
• \(8=1+2+4+1\)
• \(18=1+2+4+3\)
• \(31=1+2+4+8+16\)

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N];
int main() {int n, m, cnt = 0;cin >> n >> m;for (int i = 1; i <= n; i ++) {int a, b, s, k = 1;cin >> a >> b >> s;while (s >= k) {v[++ cnt] = k * a;w[cnt] = k * b;s -= k;k *= 2;}if (s) {v[++ cnt] = s * a;w[cnt] = s * b;}}n = cnt;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];return 0;
}

复杂度分析

• 时间复杂度：\(O(n\max\{m, \log{s}\})\)，其中\(s\)为\({s_1,s_2,...,s_n}\)的最大值。
• 空间复杂度：\(O(m+log{s})\)。

单调队列优化

以下内容使用了较多数学化表述，要求读者对完全背包的单调队列优化已有一定基础，否则可能较难理解部分推导过程。

思路

仔细观察状态转移表达式

\[f_{i,j} = \max\big\{ f_{i-1,j}, f_{i-1,j-v}+w, f_{i-1,j-2v}+2w, \dots, f_{i-1,j-sv}+sw \big\} \]

其中第\(i\)件物品的体积为\(v\)，价值为\(w\)，数量上限为\(s\)。

不难发现，\(f_{i,j}\)仅可能由满足\(j\equiv k\pmod v,\ k\le j\)的\(f_{i-1,k}\)转移而来。举例说明：设\(v=2,j=9\)，其依赖的状态分别为\(f_{i-1,9},f_{i-1,7},f_{i-1,5},f_{i-1,3},f_{i-1,1}\)，均满足\(k\equiv9\pmod2\)。

因此，可以对容量按照\(v\)取模进行分组。对于余数\(r\in\{0,1,\dots,v-1\}\)，考虑容量序列

\[r,r+v,r+2v,\dots,r+kv \]

其中\(k\)为满足\(r+kv\le m\)的最大整数。

对固定的\(r\)，令\(j=r+kv\)，则\(f_{i,j}\)只可能由\(f_{i-1,j-pv},0\le p\le s\)转移而来，于是有

\[f_{i,j} = \max_{0\le p\le s} \Big\{ f_{i-1,j-pv}+p\,w \Big\} \]

由该式可知，对于固定的\(r\)，\(f_{i,j}\)所依赖的状态构成了一个大小为\(s+1\)的离散滑动窗口，即\(\{j-sv,j-(s-1)v,\dots,j\}\)。

单调队列

由于需要维护上述滑动窗口，自然可以引入单调队列进行优化。定义队列\(q\)用于维护在当前\(r\)下、上一阶段中可能产生最优转移的容量值，从而避免对每个\(j\)重新枚举所有\(p\)。由于\(p=0\)时对应\(f_{i-1,j}\)可单独处理，因此只需维护窗口大小为\(s\)的区间\([j-sv,j-v]\)。

设队列\(q\)的队首和队尾分别为\(q_h,q_t\)，则\(j-pv=q_h\Rightarrow p=(j-q_h)/v\)，从而有

\[f_{i,j} = \max\left\{ f_{i-1,j}, f_{i-1,q_h}+\frac{j-q_h}{v}\cdot w \right\} \]

在实际实现中通常采用滚动数组优化。由于\(f_{i,j}\)依赖于上一阶段的状态，且单调队列需要按\(j\)从小到大枚举，因此定义数组\(g\)保存第\(i-1\)阶段的状态，即

\[f_j = \max\left\{ g_j, g_{q_h}+\frac{j-q_h}{v}\cdot w \right\} \]

此前假定队列\(q\)中维护的是最优转移的容量值，下面具体分析队列维护规则。分别考虑\(g_{q_t}\)与\(g_j\)在作为\(f_{j+v}\)转移来源时的情况：

• 当转移来源为\(g_{q_t}\)时

\[f_{j+v} = \max\left\{ g_{j+v}, g_{q_t}+\frac{j+v-q_t}{v}\cdot w \right\} \]

• 当转移来源为\(g_j\)时

\[f_{j+v} = \max\{g_{j+v},g_j+w\} \]

比较两种转移形式可知，只需比较\(g_j\)与\(g_{q_t}+(j-q_t)/{v}\cdot w\)的大小关系，即可确定是否将\(q_t\)从队尾弹出。

代码实现

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 20010;
int f[N], q[N], g[N];int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i ++) {int v, w, s;cin >> v >> w >> s;memcpy(g, f, sizeof(f));for (int r = 0; r < v; r ++) {int h = 0, t = -1;for (int j = r; j <= m; j += v) {if (h <= t && q[h] < j - s * v) h ++;if (h <= t) f[j] = max(g[j], g[q[h]] + (j - q[h]) / v * w);while (h <= t && g[j] >= g[q[t]] + (j - q[t]) / v * w) t --;q[++ t] = j;}   }}cout << f[m];return 0;
} 

混合背包

题目概述

给定\(n\)个物品和一个容量为\(m\)的背包，以及第\(i\)个物品的体积\(v_i\)、价值\(w_i\)和物品数量\(s_i\)。当\(s_i=-1\)时，表示该物品只有\(1\)个；当\(s_i=0\)时，表示该物品数量无限；当\(s_i>0\)时，表示该物品有\(s_i\)个。求在总容量不超过\(m\)的前提下，可获得的最大价值。

• 测试连接：7. 混合背包问题

思路

在前面几种背包问题的基础上，该问题并无额外难度。只需根据\(s_i\)的不同取值，分别按照对应的背包模型进行状态转移即可，因此这里不再展开详细讨论。

代码实现

#include <bits/stdc++.h>
using namespace std;const int N = 1110;
int f[N], q[N], g[N];
int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i ++) {int v, w, s;cin >> v >> w >> s;if (!s) {for (int j = v; j <= m; j ++) {f[j] = max(f[j], f[j - v] + w);}} else if (s == -1) {for (int j = m; j >= v; -- j) {f[j] = max(f[j], f[j - v] + w);}} else {memcpy(g, f, sizeof(f));for (int r = 0; r < v; r ++) {int h = 0, t = -1;for (int j = r; j <= m; j += v) {if (h <= t && q[h] < j - s * v) h ++;if (h <= t) f[j] = max(g[j], g[q[h]] + (j - q[h]) / v * w);while (h <= t && g[j] >= g[q[t]] + (j - q[t]) / v * w) t --;q[++ t] = j;    }}}}cout << f[m];return 0;
}

该问题中的多重背包部分同样可以采用二进制优化，这里留给读者自行实现。

复杂度分析

• 时间复杂度：\(O(nm)\)。
• 空间复杂度：\(O(n)\)。

二维费用背包

题目概述

给定\(n\)个物品和一个容量为\(m\)、承受重量为\(t\)的背包，以及第\(i\)个物品的体积\(v_i\)、重量\(u_i\)和价值\(w_i\)，求在总容量不超过\(m\)且总重量不超过\(t\)的前提下，可获得的最大价值。

• 测试连接：8. 二维费用的背包问题

思路

对比01背包问题，该问题额外引入了一个承受重量\(t\)的约束，但整体分析思路保持不变。考虑第\(i\)个物品选或不选，其决策依赖于第\(i-1\)个物品的状态，因此在每个阶段中，需要枚举前一阶段在所有可能的容量与重量组合下的状态。

直接考虑滚动数组优化，定义\(f_{j,k}\)表示总容量不超过\(j\)、总重量不超过\(k\)时的最大价值，其状态转移方程为

\[f_{j,k}=\max\{f_{j,k},f_{j-v_i,k-u_i}+w_i\} \]

代码实现

#include <bits/stdc++.h>
using namespace std;const int N = 110;
int f[N][N];
int main() {int n, m, t;cin >> n >> m >> t;for (int i = 1; i <= n; i ++) {int v, u, w;cin >> v >> u >> w;for (int j = m; j >= v; -- j) {for (int k = t; k >= u; -- k) {f[j][k] = max(f[j][k], f[j - v][k - u] + w);}}}cout << f[m][t];return 0;
}

复杂度分析

• 时间复杂度：\(O(nm)\)。
• 空间复杂度：\(O(m)\)。

分组背包

题目概述

给定\(n\)组物品和一个容量为\(m\)的背包，以及第\(i\)组物品个数\(s_i\)。对于每个\(s_i\)，给定第\(j\)个物品体积\(v_{i,j}\)及价值\(w_{i,j}\)，求总容量不超过\(m\)的选择方案的最大价值。

• 测试连接：9. 分组背包问题

思路

由于每组物品最多只能选择一个物品，可以在01背包的基础上增加一层循环枚举每组物品。该思路较为直接，因此不做过多赘述。接下来主要讨论分组背包滚动数组优化的细节。

代码实现中，枚举顺序为\(i,j,k\)，分别表示阶段、容量和物品。其中\(j\)从大到小枚举，且\(j,k\)的枚举顺序不可交换，否则会导致当前阶段的状态覆盖上一阶段的状态。需要注意的是，由于\(k\)在\(j\)内循环，所以\(j\)需要枚举到0（而不是类似01背包问题的\(v_i\)），因为在分组背包中，物品体积\(v_{i,k}\)在内层循环\(k\)中确定。

代码实现

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 110;
int f[N], v[N], w[N];int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; i ++) {int s;cin >> s;for (int j = 1; j <= s; j ++) cin >> v[j] >> w[j];for (int j = m; j; -- j) {for (int k = 1; k <= s; k ++) {if (j >= v[k]) {f[j] = max(f[j], f[j - v[k]] + w[k]);}}}}cout << f[m];return 0;
} 

复杂度分析

• 时间复杂度：\(O(nm \max\{s\})\)，其中\(s\)为\(\{s_1,s_2,...,s_n\}\)的最大值。
• 空间复杂度：\(O(m)\)。

有依赖的背包（树上背包）

题目概述

给定\(n\)组物品和一个容量为\(m\)的背包，以及第\(i\)个物品的体积\(v_i\)、价值\(w_i\)和其父节点编号\(p_i\)。物品之间具有依赖关系，且依赖关系组成一棵树的形状，如果选择一个物品，则必须选择它的父节点。求总容量不超过\(m\)的选择方案的最大价值。

• 测试连接：10. 有依赖的背包问题

思路

由于选择某个物品必须同时选择其父节点，我们不妨从根节点\(r\)开始进行决策。设根节点的体积为\(v_r\)。当背包容量\(m < v_r\)时，根节点无法被选择，问题无解；当\(m \ge v_r\)时，根节点必须选择，此时剩余可分配给其子树的容量为\(m - v_r\)。

设根节点\(r\)共有\(d\)个直接子节点，其对应的子树根节点分别为

\[s_1, s_2, \dots, s_d . \]

对每一棵子树，需要决定是否参与选择以及分配多少容量。记分配给第\(i\)棵子树的容量为\(k_i\)，则这些容量满足

\[\sum_{i=1}^{d} k_i \le m - v_r \]

不同子树之间的选择相互独立，因此问题转化为：在容量约束下，如何在各个子树之间分配容量以使得总价值最大。

为了刻画这一过程，我们依次考虑各个子树。不妨用\(s\)表示任意一个子树的根节点，设分配给该子树的容量为\(k\)，其体积和价值分别为\(v\)与\(w\)。此时有两种选择：

• 若为该子树分配容量\(k \ge v\)，则必须选择节点\(s\)，并在剩余容量\(k - v\)的约束下，取得其所有子树中的最大价值；
• 否则，无法选择节点\(s\)，且该子树中的所有节点均不能被选择，可直接跳过该子树。

由于分配给子树的容量\(k\)并不确定，其取值范围为\([0,m-v_r]\)。因此，需要预先求出以\(s\)为根的子树在不同容量约束下所能取得的最大价值。由此可见，该问题具有明显的最优子结构，各子问题的形式完全相同但规模更小；同时，由于物品之间存在一个构成树形结构的父子依赖关系，可以通过递归处理。

树结构无需显示处理边界问题，因为采用图的存储方式，没有空指针，那么当递归到叶节点，会自动返回。

当根节点\(r\)依次枚举其子树\(s_1,s_2,\dots,s_d\)时，需要同时考虑每棵子树是否被选择以及为其分配的具体容量。这一过程等价于分组背包问题：将每一棵子树视为一个物品组，不同的容量分配方案对应组内的不同物品。

综上，为形式化描述这一过程，定义状态\(f_{u,i,j}\)表示：在已选择节点\(u\)的前提下，仅考虑前\(i\)颗子树，并在容量约束为\(j\)的情况下所能获得的最大价值，其状态转移方程为

\[f_{u,i,j}=\max\{f_{u,i-1,j}, f_{u,i-1,j-k}+f_{s,d,k}\} \]

在实际情况中，可以通过分组背包的压缩方式，将状态转移方程转换压缩为

\[f_{u,j}=\max\{f_{u,j}, f_{u,j-k}+f_{s,k}\} \]

但需要注意枚举顺序。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int v[N], w[N], f[N][N];
vector<int> g[N];
int n, m, r;void dfs(int u, int lim) {for (int i = v[u]; i <= lim; i ++) f[u][i] = w[u];for (int s : g[u]) {dfs(s, lim - v[u]);for (int j = lim; j >= v[u]; -- j) {for (int k = 0; k <= j - v[u]; k ++) {f[u][j] = max(f[u][j], f[u][j - k] + f[s][k]);}}}
}int main() {cin >> n >> m;for (int i = 1; i <= n; i ++) {int p;cin >> v[i] >> w[i] >> p;if (p != -1) g[p].push_back(i); else r = i;}dfs(r, m);cout << f[r][m];return 0;
}

背包求方案数

题目概述

给定\(n\)个物品和一个容量为\(m\)的背包，以及第\(i\)个物品体积\(v_i\)，价值\(w_i\)，每个物品只有一个，求总容量不超过\(m\)的选择方案的最大价值所对应的方案数，由于数量可能很大，需要对$ 10^9+7$取模。

• 测试连接：11. 背包问题求方案数

思路

由于已知\(f_{n,m}\)表示最大价值，一个显然的事实是，所有能转移到\(f_{n,m}\)的状态表示\(f_{n,m}\)的方案数，于是记录在转移过程中所有可以到达\(f_{n,m}\)的状态即可。

定义\(c_{i,j}\)表示\(f_{i,j}\)所对应的方案数，设第\(i\)阶段的物品容量为\(v_i\)，价值为\(w_i\)，则\(c_{i,j}\)所对应的转移方程

\[c_{i,j}=\begin{cases} c_{i-1,j}, \quad f_{i,j}< f_{i-1,j-v_{i}}+w_i \\ c_{i-1,j}+c_{i-1,j-v_i}, \quad f_{i,j}=f_{i-1,j-v_{i}+w_i} \end{cases} \]

定义初始条件：\(c_{0,j}=1, \ \forall j\in [0,m]\)，表示一个都不选的方案数。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N], c[N];int main() {int n, m;cin >> n >> m;for (int i = 0; i <= m; i ++) c[i] = 1;for (int i = 1; i <= n; i ++) {int v, w;cin >> v >> w;for (int j = m; j >= v; -- j) {int x = f[j - v] + w;if (x > f[j]) {f[j] = x;c[j] = c[j - v];} else if (x == f[j]) {c[j] = (c[j] + c[j - v]) % mod;}}}   cout << c[m];return 0;
} 

• 时空复杂度同01背包，不做过多讨论。

背包求具体方案

给定\(n\)个物品和一个容量为\(m\)的背包，以及第\(i\)个物品体积\(v_i\)，价值\(w_i\)，每个物品只有一个，求总容量不超过\(m\)的选择方案的最大价值所对应的具体方案，要求字典序最小。

• 测试连接：12. 背包问题求具体方案

思路

在经典01背包中，状态转移方程为

\[f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i\} \]

但若需要恢复具体选取方案，则必须保留完整的阶段信息，以便在状态表中回溯决策过程。

为此，我们重新定义状态：令\(f_{i,j}\)表示考虑物品从\([n,i]\)，且容量约束为\(j\)的前提下，所能获得的最大价值。对应的转移方程为

\[f_{i,j}=\max\{f_{i+1,j},f_{i+1,j-v_i}+w_i\} \]

于是，当回溯\(f_{i,j}\)时，有三种情况：

• 若\(f_{i,j}=f_{i+1,j}\)：则表示第不选\(i\)个物品；
• 若\(f_{i,j}=f_{i+1,j-v_i}+w_i\)：则表必须选第\(i\)个物品；
• 若\(f_{i,j}=f_{i+1,j}=f_{i+1,j-v_i}+w_i\)：则既可以选也可以不选，但选择了该物品字典序更小。

因为从大到小进行回溯决策，且该决策是在全局最优的情况下进行的，且每一步均保持最优性，因此最终构造出的方案是全局最优解。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N], 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 = n; i; -- 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]);}}}    int j = m;for (int i = 1; i <= n; i ++) {if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {cout << i << ' ';j -= v[i];}}return 0;
} 

复杂度分析

• 时间复杂度：同01背包。
• 空间复杂度：\(O(nm)\)，由于无法用滚动数组。

其他

恰好装满的背包（01背包）

对背包问题进行一个扩展，介绍另外一种状态定义方式。

在前面，我们知道在对第\(i\)个阶段在\(j\)容量下的决策的最大价值依赖前\(i-1\)阶段决策后容量约束为\(j-v_i\)的最大价值。

事实上，当\(n\)阶段决策后，最优解一定在某个确定的\([0,m]\)的容量中，假设其为\(j\)，考虑第\(n\)个物品的两种决策方式：

• 若没有拿\(n\)阶段的物品，则最大价值等于前\(n-1\)阶段决策后容量恰好为\(j\)的价值；
• 若拿了\(n\)阶段的物品，设第\(n\)阶段的容量为\(v\)，则最大价值等于前\(n-1\)阶段决策后容量恰好为\(j-v\)的价值。

于是定义状态\(f_{i,j}\)表示考虑前\(i\)个物品，且总容量恰好为\(j\)的最大价值。由于\(1\)起始阶段，设其容量为\(v_1\)，需要定义初始状态\(f_{1,0},f_{1,v_1}\)。不过注意到，这两个状态都可以由\(f_{0,0}\)转移，于是定义初始条件：\(f_{0,0}=0,f_{i,j}=-\infty, \ \forall i,j\)，状态转移方式不变。

滚动数组优化方式以及时空复杂度和前面相同，不在赘述。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N];
int main() {int n, m;cin >> n >> m;memset(f, -0x3f, sizeof(f));f[0] = 0;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]);}}int ans = 0;for (int i = 0; i <= m; i ++) ans = max(ans, f[i]);cout << ans;return 0;
}

• 其他背包问题也可以使用该状态定义方式计算。