文章目录
一、背包问题
1. 背包问题简介
2. 背包问题解决方法
二、01 背包问题
1. 实现思路
2. 实现代码
三、完全背包问题
1. 实现思路
2. 实现代码
四、多重背包问题（一）
1. 实现思路
2. 实现代码
五、多重背包问题（二）
1. 实现思路
2. 实现代码
六、分组背包问题
1. 实现思路
2. 实现代码
一、背包问题
1. 背包问题简介
背包问题可以理解为，给定一个背包容量 target，再给定一个数组 nums（用以表示物品），能否按一定方式选取 nums 中的元素得到 target。
这里需要注意的有以下几点：
（1） 背包容量 target 和物品 nums 的类型可能是数，也可能是字符串。
（2） target 可能题目已经给出（显式），也可能是需要我们从题目的信息中挖掘出来（非显式）（常见的非显式 target 比如 sum/2 等）。
（3） 选取方式有常见的一下几种：每个元素选一次/每个元素选多次/选元素进行排列组合 那么对应的背包问题就是下面我们要讲的背包分类。
背包问题主要可以分为四类，分别是：01 背包问题，完全背包问题，多重背包问题和分组背包问题。
- （1） 01 背包问题
- 01 背包问题是一种非常经典的背包问题。
2. 背包问题解决方法
对于上述问题，我们常使用动态规划解决此类问题。
动态规划总共包括两大部分，分别是状态表示（判断是几维，两维就是 f ( i , j ) f(i,j)f(i,j)，每一个状态的含义是什么）和状态计算（如何计算出每一个 f ( i , j ) f(i,j)f(i,j)）。
动态规划的优化通常都是对代码或者计算方程进行等价变化。
f ( i , j ) f(i,j)f(i,j) 表示的选择方法只指从前 i ii 个物品中选和总体积不超过 j jj。
状态表示可分为集合（每一个状态表示的都是一个集合）和属性（包括最大值，最小值，元素的数量，我们的背包问题就是属性当中的最大值）。
状态计算对应的是集合的划分（每一个元素当前只会属于一个集合，每一个元素都存在），将 f ( i , j ) f(i,j)f(i,j) 划分为若干个子集和，每一个子集合都可以由更小的子集合表示。
二、01 背包问题
题目描述
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8
具体实现
1. 实现思路
2. 实现代码
#include#include <bits/stdc++.h> using namespace std; const int N = 1010; //n, m表示物品种数和背包体积 int n, m; //v[N], w[N]表示物品的体积和价值 int v[N], w[N]; //f[N][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]) //如果可以装下当前第i个物品 { f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); } } } cout << f[n][m] << endl; return 0; }
三、完全背包问题
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
10
具体实现
1. 实现思路
完全背包问题和 01 背包问题的区别在于完全背包问题当中的物品可以被选择无数次。
完全背包问题可以选择使用一维或二维进行解决，如果直接使用与 01 背包问题相同的方法是三个 for 循环，此时会超时，就需要进行优化。
那么，f [ i ] f[i]f[i] 就表示体积是 i ii 的情况下，最大价值是多少（状态表示）。
f [ 0 … … m ] f[0……m]f[0……m] 当中的最大值就是我们所求的结果。
2. 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 1010; //n, m表示物品数量和背包体积 int n, m; //v[N], w[N]表示物品的体积和价值 int v[N], w[N]; //f[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 = v[i]; j <= m; j ++ ) { f[j] = max(f[j], f[j - v[i]] + w[i]); } } cout << f[m] << endl; return 0; }
四、多重背包问题（一）
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例
10
具体实现
1. 实现思路
多重背包问题与上述两种背包问题的区别在于每个物品最多有 s i此题与 01 背包问题基本相同。
2. 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 110; //n, m表示物品种数和背包体积 int n, m; //v[N], w[N]，s[N]表示物品的体积，价值，数量 int v[N], w[N], s[N]; //f[N][N]表示价值 int f[N][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 - v[i] * k] + w[i] * k); } } } cout << f[n][m] << endl; return 0; }
五、多重背包问题（二）
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例
10
具体实现
1. 实现思路
多重背包问题（二）与多重背包问题（一）的区别在于（二）的数据范围进行了扩大，如果直接暴力做法会导致超时，因此，需要进行优化。
由于（一）当中的做法与 01 背包问题基本相同，所以，我们只需要对与 01 背包问题相同的那一段进行优化。
这里引入二进制优化方法（用二进制表示十进制）。
举例说明，如果我们要从 0 枚举到 1023，十进制的做法需要我们枚举 1023 次，如果采用二进制做法，我们需要将 1023 分成十组，分别是 1，2，4，8，16，32，64，128，256 和 512，我们在这十组数字当中，每组任意取出一个数字，组合起来就可以得到 0 到1023 当中的任何数字，此时，我们只需要枚举 10 次即可。
2. 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 12010, M = 2010; //n，m表示物品种数和背包容积 int n, m; //v[N], w[N]表示每组物品的总体积和总价值 int v[N], w[N]; //f[M]表示价值 int f[M]; int main() { cin >> n >> m; //二进制枚举 int cnt = 0;//将物品重新分组后的顺序 for (int i = 1; i <= n; i ++ ) { //a, b, s表示是每种物品的体积、价值和数量。 int a, b, s; cin >> a >> b >> s; int k = 1; //二进制拆分，打包时每组中有 k 个同种物品 while (k <= s) //最后一组的物品个数 < 2^(n+1) 1 2 4 8 16 ... 2^n 2^(n+1) { cnt ++ ; v[cnt] = a * k;// 每组的体积 w[cnt] = b * k;// 每组的价值 s -= k; //得到剩余的物品数量 k *= 2;// 注意是 k * 2，每次增长一倍，不是k * k } if (s > 0)// 二进制拆分完之后 剩下的物品个数分为新的一组 { cnt ++ ; v[cnt] = a * s; w[cnt] = b * s; } } 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] << endl; return 0; }
六、分组背包问题
题目描述
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例
8
具体实现
1. 实现思路
分组背包问题是指我们有 N NN 组物品，每组物品当中有若干个物品，每个物品的体积和价值各有不同，每组物品当中最多只能选一个（可以不选）
2. 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 110; //n，m表示物品组数和背包容积 int n, m; //v[N][N], w[N][N], s[N]表示物品的体积，价值和数量 int v[N][N], w[N][N], s[N]; //f[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 (v[i][k] <= j) { f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]); } } } } cout << f[m] << endl; return 0; }
