【算法精练】背包问题（01背包问题）
目录
1. 背包问题
2. 01背包问题
3. 优化
总结
1. 背包问题
经典的背包问题：
有一个背包，限制背包的体积；有一堆物品，从这堆物品中选择，在不超过背包容量的前提下，选出最大价值的物品；
从这个问题中可以提取出两个关键的信息：1、物品属性 2、背包属性
比如：有一个背包大小是7，有以下物品：
从中选出最大价值；背包也有划分：1. 必须装满、2. 不需要装满；
01背包问题：这些物品中，每种物品只有一个（也就是只能选择一次）
完全背包问题：物品有无穷个（可重复选择）；
2. 01背包问题
以这道模板题为例：
题目链接：
DP41 【模板】01背包
这道题有两问：
- 求这个背包至多能装多大价值的物品?
- 若背包恰好装满，求至多能装多大价值的物品?
先来看第一问：
以示例一为例:
背包可容纳的体积为5，有以下物品可以选择：分别为1号、2号、3号；
背包问题属于经典的动态规划，而动态规划有一个经典的特征：递推；直白的说就是：可以通过先前的状态，来得到当前所求的状态；进而一种地推得到最终结果；然而每个地推的过程都是一个相同的子问题，这一点和递归搜索算法也有些类似；对于动态规划问题的解决，核心在于状态表示，即：dp所表示的含义，根据状态表示进而推导出状态转移方程；因此背包问题也是符合这一规律的；
动态规划的问题解决基本包含三大步骤：
- 状态表示
- 状态转移方程推导
- 初始化dp表
状态表示：
状态的表示往往是根据题目要求而设定的，当然新手很可能无法一次就找准状态表示，但可以通过经验进行总结，一些相似的问题或者一类问题状态表示都具有一定的相似性（规律），掌握这些可以更好的帮助我们解决问题；
较为直白的一些动态规划，一般题目就包含所需的状态表示，比如：
实例中的问题一：求这个背包至多能装多大价值的物品？（不超过背包容量的前提下）；
程序不像人一样可以思考，从物品中选择最合适的，只能挨个遍历，然后根据规律判断是否选择；
这里的核心点就如上加粗部分，因此就可以设状态表示：在前 i 个物品中选择，在不超过体积 j 的情况下，所能选出的最大价值；
状态转移方程的推导：
有了状态表示，接下来就是状态转移方程的推导；状态转移方程的推导核心在于状态的分析，比如：在前 i 个物品中选择，在不超过体积 j 的情况下，所能选出的最大价值；
在前i个物品中选，对于一个物品，就有两种选择：1、选；2、不选
根据这里就可以推出转移方程：
dp[i][j]：在前 i 个物品中选择，在不超过体积 j 的情况下，所能选出的最大价值；
1. 选第i个物品：如果选第 i 个物品，那么 dp[i-1][j - v[i]]就需要存在；
dp[i-1][j - v[i]]：在前i - 1个物品中选，体积不超过 j - v[i]，所能选出的最大价值；
dp[i][j] = dp[i-1][j - v[i]] + w[i]；
2. 不选第i个物品：如果不选第 i 个物品：dp[i-1][j]；dp[i-1][j]：在前i - 1个物品中选，体积不超过 j ，所能选出的最大价值；
dp[i][j] = dp[i-1][j - v[i]] + w[i]；
dp[i][j] = dp[i-1][j]；
两种情况选择最大值：dp[i][j] = max(dp[i-1][j - v[i]] + w[i] , dp[i-1][j]);
初始化dp表：
主要分析以下几：
1、边界：0， 1， n（最大边界），也就是极端情况；
2、下标访问是否越界；
3、初始化数据不能影响后续结果的选择；
状态转移方程：dp[i][j] = max(dp[i-1][j - v[i]] + w[i] , dp[i-1][j]);
dp[i-1][j - v[i]] ： j - v[i]可能小于0，小于0表示体积为负，这显然是不存在的；
初始化时的数据：求的是最大值（max），dp表初始化的数据要足够小，但也不能为负数；取0最合适；
代码：
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
int dp[N][N];
int main() {
int n, V;
cin >> n >> V;
vector<int> v(n + 1), w(n + 1);
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= V; j++){
dp[i][j] = dp[i-1][j];
if(j - v[i] >= 0){
dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i]);
}
}
}
cout << dp[n][V] << endl;
}第二问：若背包恰好装满，求至多能装多大价值的物品?
有了第一问的经验，得出第二问的状态表示就简单许多；
状态表示(dp)：在前 i 个物品中选择，体积刚好为 j ，能选出的最大价值；
状态转移方程：
也是分为两种情况：1、选；2、不选
选：dp[i][j] = dp[i-1][j - v[i]] + w[i]；
不选：dp[i][j] = dp[i-1][j];
唯一不同的就是需要有一个状态的，去表示某个状态存在；
状态转移方程依然是：dp[i][j] = max(dp[i - 1][j], dp[i-1][j - v[i]] + w[i]);
但需要添加限制条件：第一问中体积不超过 j，不超过j其中也包含刚好为 j；体积要想刚好为j，那么 dp[i-1][j - v[i]] 必须要存在；
dp[i-1][j - v[i]]: 在前 i - 1 个物品中选择，体积刚好为 j - v[i] ，能选出的最大价值；
如何标识？0肯定不能选，选择 - 1；如果某个状态的值为 -1，表示该状态不存在；
初始化：初始化也并非是将所有的值都初始化为 -1，这样会影响后续数据的选择，只需将初始化（最开始）时的一些不存在的状态初始化为 -1；
也就是 dp[0][j]，从前0个物品中选体积为j，怎么选都不可能选出，因此状态不可能存在；如果后续状态依然不存在，dp[i][j] = dp[i-1][j];依然会等于 -1；
第二问也就解决了，代码：
memset(dp, 0, sizeof dp);
for(int i = 1; i < V; i++) dp[0][i] = -1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= V; j++){
dp[i][j] = dp[i-1][j];
if(j - v[i] >= 0 && dp[i-1][j - v[i]] != -1){
dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i]);
}
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;总体代码：
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1010;
int dp[N][N];
int main() {
int n, V;
cin >> n >> V;
vector<int> v(n + 1), w(n + 1);
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= V; j++){
dp[i][j] = dp[i-1][j];
if(j - v[i] >= 0){
dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i]);
}
}
}
cout << dp[n][V] << endl;
memset(dp, 0, sizeof dp);
for(int i = 1; i < V; i++) dp[0][i] = -1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= V; j++){
dp[i][j] = dp[i-1][j];
if(j - v[i] >= 0 && dp[i-1][j - v[i]] != -1){
dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i]);
}
}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
}
3. 优化
看总体代码会发现一个问题：dp在访问时只会访问前一行的dp数据（dp[i-1]），之后就不会访问了，开一个二维数组空间显然是很浪费的；因此可以进行滚动优化；
已经填过的数据不会再使用了，所以这里可以不断的滚动数组，来进行空间的优化;但是使用两个数组进行滚动，还是有些空间浪费，使用一个数组即可；填过一遍数组后，再重新开始填下一轮，当前表中的数据就是下一轮所需的数据；但是需要考虑数据被覆盖的问题；
在访问时，只使用了dp[i-1][j]，dp[i-1][j-v[i]]；因此填表的顺序需要改变一下；显然 j - v[i] <= j；
因此正着填表必然会导致数据被覆盖；dp[i][j] = max(dp[i - 1][j], dp[i-1][j - v[i]] + w[i]); 把dp[i] 和dp[i-1]看成同一个数组，要更新 j 位置就需要原先的 j 位置 和 j - v[i] 位置的数据；怎么避免覆盖？从右向左进行填表；
代码：
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1010;
int dp[N];
int main() {
int n, V;
cin >> n >> V;
vector<int> v(n + 1), w(n + 1);
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++){
for(int j = V; j >= 1; j--){
if(j - v[i] >= 0){
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
cout << dp[V] << endl;
memset(dp, 0, sizeof dp);
for(int i = 1; i <= V; i++) dp[i] = -1;
for(int i = 1; i <= n; i++){
for(int j = V; j >= 1; j--){
if(j - v[i] >= 0 && dp[j - v[i]] != -1){
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
}辨别01背包问题：
在前 i 个中（0~i）选择，刚好为 j (或者不超过j）....；并且数据只能选择一次，不可重复选择；这些都属于01背包问题，有些需要将问题进行转化，转化成01背包问题，有些则较为直白能直接看出；01背包问题的状态表示基本就是以上的结构，至于状态转移方程的推导，需要结合题目进行分析；唯有多加练习；
总结
好了以上便是本文的全部内容，希望对你有所帮助，感谢阅读！