DAY35|动态规划Part03|LeetCode:01背包问题二维、01背包问题一维、416. 分割等和子集

01背包理论基础（一）

基本思路

C++代码

01背包理论基础（二）

基本思路

C++代码

LeetCode:416. 分割等和子集

基本思路

C++代码

01背包理论基础（一）

题目链接：卡码网46. 携带研究材料

文字讲解：01背包理论基础

视频讲解：带你学透0-1背包问题！

对于面试的话，其实掌握01背包和完全背包，就够用了，最多可以再来一个多重背包。

背包问题的理论基础重中之重是01背包，一定要理解透！

首先对于暴力解法，每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。很容易超时，因此需要使用动态规划的方法进行优化！

以下表为例，问背包能背的物品最大价值是多少？

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

基本思路

动规五部曲分析如下：

确定dp数组以及下标的含义

我们需要使用二维数组，为什么呢？因为有两个维度需要分别表示：物品和背包容量。如图，二维数组为 dp[i][j]。

其中，i 来表示物品、j表示背包容量。dp[i][j]表示在物品[0,i]中，任意选取一个或多个物品，装进容量为j的背包中时能够满足条件的最大价值。

确定递推公式

对于第i个物品，我们可以选择不放入背包和放入背包两种情况。如果不放入背包，那么此时最大价值应该为dp[i-1][j]；如果放入背包，那么就应该先将背包容量减去weight[i]，然后加上value[i]。将两者比较取最大值，即为背包所能装取物品的最大价值。

即dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp数组如何初始化

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

确定遍历顺序

先遍历物品还是先遍历背包重量呢？其实都可以！！但是先遍历物品更好理解。

//先遍历物品，在遍历背包
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品for(int j = 0; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}//先遍历背包，在遍历物品
// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量for(int i = 1; i < weight.size(); i++) { // 遍历物品if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

举例推导dp数组

来看一下对应的dp数组的数值，如图：

最终结果就是dp[2][4]。

C++代码

#include <bits/stdc++.h>
using namespace std;int main() {int n, bagweight;// bagweight代表行李箱空间cin >> n >> bagweight;vector<int> weight(n, 0); // 存储每件物品所占空间vector<int> value(n, 0);  // 存储每件物品价值for(int i = 0; i < n; ++i) {cin >> weight[i];}for(int j = 0; j < n; ++j) {cin >> value[j];}// dp数组, dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化, 因为需要用到dp[i - 1]的值// j < weight[0]已在上方被初始化为0// j >= weight[0]的值就初始化为value[0]for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}for(int i = 1; i < weight.size(); i++) { // 遍历科研物品for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}cout << dp[n - 1][bagweight] << endl;return 0;
}

01背包理论基础（二）

题目链接：卡码网46. 携带研究材料

文字讲解：01背包理论基础（二）

视频讲解：带你学透01背包问题（滚动数组篇）

基本思路

通过01背包问题理论基础（一）的讲解，仔细琢磨，就会发现其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

进一步，动规五部曲分析如下：

确定dp数组以及下标的含义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

确定递推公式

一维dp数组，其实就上一层 dp[i-1] 这一层拷贝的 dp[i]来。

递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp数组如何初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。根据上面的递推公式，dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

确定遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

这里的遍历顺序和二维dp数组不同。二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。这是因为一维dp，本质上还是在遍历一个二维数组，只不过是在不断地对价值进行更新，如果我们从小到大进行遍历，就可能会导致一个物品被多次放入。

另外，对于两层for循环，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？其实是不可以的，因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

举例推导dp数组

一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下：

C++代码

// 一维dp数组实现
#include <iostream>
#include <vector>
using namespace std;int main() {// 读取 M 和 Nint M, N;cin >> M >> N;vector<int> costs(M);vector<int> values(M);for (int i = 0; i < M; i++) {cin >> costs[i];}for (int j = 0; j < M; j++) {cin >> values[j];}// 创建一个动态规划数组dp，初始值为0vector<int> dp(N + 1, 0);// 外层循环遍历每个类型的研究材料for (int i = 0; i < M; ++i) {// 内层循环从 N 空间逐渐减少到当前研究材料所占空间for (int j = N; j >= costs[i]; --j) {// 考虑当前研究材料选择和不选择的情况，选择最大值dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);}}// 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值cout << dp[N] << endl;return 0;
}

LeetCode:416. 分割等和子集

力扣代码链接

文字讲解：LeetCode:416. 分割等和子集

视频讲解：动态规划之背包问题，这个包能装满吗？

基本思路

看到这类题目和容易想到之前做过的---698.划分为k个相等的子集这类题目，可以采用回溯法进行暴力求解，但是使用回溯法的时间复杂度是指数级别的（即集合中的每个数都存在选择和不选择两种状态，因此时间复杂度为2^n），会超时，因此需要进行优化。这里可以使用01背包进行求解（每个元素只使用一次）。

动规五部曲分析如下：

确定dp数组以及下标的含义

可以使用一维dp，也可以使用二维dp,为了减小空间复杂度，这里使用一维dp数组。其中dp[j] 表示：容量为j的背包，所背的物品价值最大可以为dp[j]。本题中每一个元素的数值既是重量，也是价值。

确定递推公式

本题中每一个元素的数值既是重量，也是价值。所以前面的递推公式中的weight[i]和value[i]都可以使用nums[i]进行替换。因此递推公式为：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

dp数组如何初始化

从dp[j]的定义来看，首先dp[0]一定是0。如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

确定遍历顺序

在一维dp数组的遍历顺序中提到，如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}
}

举例推导dp数组

dp[j]的数值一定是小于等于j的。如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

用例1，输入[1,5,11,5] 为例，如图：

最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。

C++代码

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;// dp[i]中的i表示背包内总和// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了vector<int> dp(10001, 0);for (int i = 0; i < nums.size(); i++) {sum += nums[i];}// 也可以使用库函数一步求和// int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 == 1) return false;int target = sum / 2;// 开始 01背包for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}// 集合中的元素正好可以凑成总和targetif (dp[target] == target) return true;return false;}
};