代码随想录算法训练营第四十二天 | 01背包问题，你该了解这些、01背包问题，你该了解这些 滚动数组、 416. 分割等和子集

打卡第42天，搞搞01背包。

今日任务

• 01背包问题，你该了解这些！
• 01背包问题，你该了解这些！ 滚动数组
• 416.分割等和子集

背包问题1.0 ：0-1 背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

暴力的解法应该是怎么样的呢？

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是$o(2^n)$，这里的n表示物品数量。

所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 $v_i$,$w_i$，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤1000

0<$v_i$,$w_i$≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

代码随想录

1. 确定 dp 以及下标定义
   dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。
   

2. 确定递推公式
   两个方向推出来dp[i][j]

   不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)

   放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

   所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. 初始化
   首先从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物品。

4. 确定遍历顺序
   二维数组的情况下 先遍历背包跟先遍历重量都可以
   一维数组的情况下 先遍历重量

5. 推导
   

#include <bits/stdc++.h>using namespace std;int main() {int n, v;scanf("%d %d", &n, &v);vector<int> weight(n);vector<int> value(n);for(int i = 0; i < n; i++) {scanf("%d", &weight[i]);scanf("%d", &value[i]);}// 初始化vector<vector<int>> dp(n, vector<int>(v + 1, 0));for(int i = weight[0]; i <= v; i++) {dp[0][i] = value[0];}for(int i = 1; i < n; i++) {for(int j = 1; j <= v; j++) {if(j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);}}printf("%d", dp[n - 1][v]);return 0;
}

优化空间（滚动数组）

我们可以发现想知道dp[i][j] ，需要知道dp[i - 1][j - weight[i]] 和 dp[i - 1][j]，都只是前一层的信息，所以我们可以用一个一维数组来保存信息，只不过我们的遍历顺序第一次遍历的是物品，第二层遍历的是背包，而且是从大到小遍历，因为想要知道大重量背包的最大价值总和，要知道前面的小重量背包的最大价值总和，而我们是用滚动数组保存，如果从小到大遍历，会改变小重量背包的最大价值总和。

#include <bits/stdc++.h>using namespace std;int main() {int n, v;scanf("%d %d", &n, &v);vector<int> weight(n);vector<int> value(n);for(int i = 0; i < n; i++) {scanf("%d", &weight[i]);scanf("%d", &value[i]);}// 初始化vector<int> dp(v + 1, 0);for(int i = weight[0]; i <= v; i++) {dp[i] = value[0];}for(int i = 1; i < n; i++) {for(int j = v; j >= 1; j--) {if(j < weight[i]) dp[j] = dp[j];else dp[j] = max(dp[j - weight[i]] + value[i], dp[j]);}}printf("%d", dp[v]);return 0;
}

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

我的题解

回溯暴力搜索，超时了哈哈哈

class Solution {
public:bool backtracking(vector<int>& nums, int sum, int starIndex) {if(sum == 0) return true;if(sum < 0) return false;for(int i = starIndex; i < nums.size(); i++) {sum -= nums[i];if(backtracking(nums, sum, i + 1)) return true;sum += nums[i];}return false;}bool canPartition(vector<int>& nums) {int sum = 0;for(int num : nums) sum += num;if(sum % 2 == 1) return false;sort(nums.begin(), nums.end());return backtracking(nums, sum / 2, 0);}
};

01背包做法，但是不是很理解。

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(int num : nums) sum += num;if(sum % 2 == 1) return false;vector<int> dp(sum / 2 + 1, 0);for(int i = nums[0]; i <= sum / 2; i++) dp[i] = nums[0]; // 初始化for(int i = 1; i < nums.size(); i++) {for(int j = sum / 2; j >= 1; j--) {if(j < nums[i]) dp[j] = dp[j];else dp[j] = max(dp[j - nums[i]] + nums[i], dp[j]);}}return dp[sum / 2] == sum / 2;}
};

代码随想录

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;}
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)，虽然dp数组大小为一个常数，但是大常数