【算法精练】背包问题（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背包问题的状态表示基本就是以上的结构，至于状态转移方程的推导，需要结合题目进行分析；唯有多加练习；