算法简述
背包问题是一类经典的动态规划问题，背包问题分为：01背包问题，完全背包问题，多重背包问题和分组背包问题。这一类问题，我们可以使用闫式分析法，借鉴yxc大佬的思路创作的博客，以便自己复习和思考。
一、01背包问题（链接）
1.1 问题描述
1.2 二维
1.2.1 二维思路讲解
这是属于动态规划问题，我们一般可以从两个方面来分析动态规划问题：状态表示和状态计算。状态表示中分为：集合和属性。
我们来先确定这个问题的集合：因为在题目中，我们可以知道时从N件物品中挑选出一些物品，且这些物品的总体积不超过背包容量，我们需要2个变量来进行表示状态：f[i][j] 表示的是我只从前 i 个物品中挑选出，且挑选出物品的总体积不超过 j。再来确定属性：因为存储的信息越少，越容易实现，所以一般情况下，这个属性是最大值、最小值……。
状态计算也就是计算状态转移方程：我们需要根据题目要求来确定我们这个状态可以分为哪几种状态。通俗一点，也可以是集合划分。01背包问题是一个物品到底选不选，如果你不选择第i个物品就相当于在i - 1的物品中选择；如果你选择第i个物品就相当于我先都不选这个物品，那么这次的体积就不包含第i个物品的体积，我先算出这个种情况下，前i - 1个物品中的最大价值，之后再加入第i个物品的价值。
1.2.2 二维思路代码实现
#include <iostream> #include <algorithm> #include <string> #include <cstring> 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]; // 不选i的情况 if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); // 选i的请//况 } } cout << f[n][m] << endl; return 0; }
1.3 一维
1.3.1 一维思路讲解
就是在二维思路的基础上将数据压缩为一维，如何压缩呢？就是将第i层不要，就是这种数据类似于滚动数组的概念，只需要很少的数组来实现循环。
1.3.2 一维思路代码实现
#include <iostream> #include <algorithm> #include <cstring> #include <string> 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; }
二、完全背包问题（链接）
2.1 问题描述
2.2 二维
2.2.1 二维思路讲解（朴素做法）
完全背包与01背包不一样的是：完全背包中的物品都可以无限次的取，而01背包中的物品只可以取一次，所以完全背包问题中的集合划分会比01背包问题的集合划分多的多的多。还是老方法，画出状态表示和状态计算。
前面思路与01背包问题大差不差，只有在集合划分与01背包不同。这个物品也不是无限次的选取，而是在选出物品的总体积不超过背包的总容量。在朴素做法中，我们是将选取的方案用循环表示，即三重循环。
2.2.2 二维思路代码实现（朴素做法）
#include <iostream> #include <algorithm> #include <cstring> #include <string> 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++) { 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; }
2.3 优化版本
2.3.1 优化版本思路讲解
我们可以发现一个规律：就是我们如果写出将j减去v[i]的话，与f[i][j]之间的关系：f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - k*v] + k*w……f[i - 1][j - s*v] + s*w)（其中s*v小于等于m），那么f[i][j - v] = max(f[i - 1][j - v] + w, f[i - 1][j - k*v] + k*w……f[i - 1][j - s*v] + s*w)（其中s*v小于等于m）。总结上述的式子，我们可以发现f[i][j] = max(f[i - 1][j], f[i][j - v] + w)。
2.3.2 优化版本代码实现
一维写法 #include <iostream> #include <algorithm> #include <string> #include <cstring> 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 = v[i]; j <= m; j++) { f[j] = max(f[j], f[j - v[i]] + w[i]); } } cout << f[m] << endl; return 0; }
