代码随想录算法训练营第三十四天| 研究携带材料、416. 分割等和子集
解题思路：动态规划（二维）
具体思路：
首先读取物品数量 m 和背包容量 n，再分别读取 m 个物品的重量数组 weight 和价值数组value，接着初始化一个 m * (n + 1) 的二维 dp 数组，dp[i][j] 表示前 i + 1个物品放入容量为j的背包能获得的最大价值，并初始化第一行当背包容量 j 大于等于第一个物品重量时，dp[0][j] 赋值为第一个物品的价值，然后通过双层循环遍历剩余物品和所有容量，若当前容量 j 小于第 i 个物品重量，则无法放入该物品，dp[i][j] 等于上一行同列的值，即不选该物品的最大价值，否则取不选该物品dp[i - 1][j] 和选该物品dp[i - 1][j - weight[i]] + value[i]中的较大值更新dp[i][j]，最终输出dp[m - 1][n]，即所有物品放入容量为 n 的背包能获得的最大价值。
具体代码：
#include<iostream> #include<vector> using namespace std; int main () { int m; int n; cin >> m >> n; vector<int> weight(m, 0); vector<int> value(m, 0); for (int i = 0; i < m; i++) cin >> weight[i]; for (int i = 0; i < m; i++) cin >> value[i]; vector<vector<int>> dp(m, vector<int>(n + 1, 0)); for (int i = weight[0]; i <= n; i++) dp[0][i] = value[0]; for (int i = 1; i < m; i++) { for (int j = 0; j <= n; 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]); } } cout << dp[m - 1][n]; return 0; }时间复杂度：O（m * n）
空间复杂度：O（m * n）
解题思路：动态规划（一维）
具体思路：
首先读取物品数量 m 和背包容量 n，再分别读取 m 个物品的重量数组 weight 和价值数组value，接着初始化一个长度为 n + 1 的一维 dp 数组，dp[j] 表示容量为 j 的背包能装下的最大价值，初始值全为 0，然后通过双层循环遍历物品和背包容量，外层循环逐个遍历 m 个物品，内层循环从后往前遍历背包容量从 n 到当前物品重量 weight[i]，这样能避免重复选取同一物品，对于每个容量 j ，取不选当前物品保持dp[j] 原值和选当前物品dp[j - weight[i]] + value[i]，即容量 j - weight[i] 的最大价值加上当前物品价值中的较大值更新 dp[j]，最终输出 dp[n] ，即容量为 n 的背包能获得的最大价值。
具体代码：
#include<iostream> #include<vector> using namespace std; int main () { int m; int n; cin >> m >> n; vector<int> weight(m, 0); vector<int> value(m, 0); for (int i = 0; i < m; i++) cin >> weight[i]; for (int i = 0; i < m; i++) cin >> value[i]; vector<int> dp(n + 1, 0); for (int i = 0; i < m; i++) { for (int j = n; j >= weight[i]; j--) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } cout << dp[n]; return 0; }时间复杂度：O（m * n）
空间复杂度：O（n）
解题思路：动态规划（二维）
具体思路：
首先计算数组所有元素的总和，若总和为奇数则直接返回 false，无法分割为两个和相等的子集，若为偶数则将目标值 target 设为总和的一半，即需找到子集和为 target，接着初始化一个二维 dp 数组 dp[i][j] 表示前 i + 1 个元素中选取若干个，能组成的不超过 j 的最大和，并初始化第一行，当 j 大于等于第一个元素值时，dp[0][j] 赋值为该元素值，然后通过双层循环遍历剩余元素和所有可能的和，若当前 j 小于第 i 个元素值，则无法选取该元素， dp[i][j] 等于上一行同列值，否则取不选该元素 dp[i - 1][j] 和选该元素 dp[i - 1][j - nums[i]] + nums[i] 的较大值更新 dp[i][j] ，过程中若发现 dp[i][j] 等于 target 则提前返回 true，若遍历结束未找到则返回 false。
具体代码：
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for(int i = 0; i < nums.size(); i++) sum += nums[i]; if(sum % 2) return false; int target = sum / 2; vector<vector<int>> dp(nums.size(), vector<int>(target + 1, 0)); for (int j = 0; j <= target; j++) if (j >= nums[0]) dp[0][j] = nums[0]; for (int i = 1; i < nums.size(); i++) { for (int j = 1; j <= target; j++) { if (j < nums[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]); if (dp[i][j] == target) return true; } } return false; } };时间复杂度：O（n * target）
空间复杂度：O（n * target）
解题思路：动态规划（一维）
具体思路：
首先计算数组所有元素的总和，若总和为奇数则直接返回 false，无法分割为两个和相等的子集，若为偶数则将目标值 target 设为总和的一半，即需找到子集和为 target，接着初始化长度为 target + 1的一维 dp 数组 dp[j] 表示选取若干元素能组成的不超过 j 的最大和，初始值全为 0，然后通过双层循环遍历数组元素和目标和，外层逐个遍历数组元素，内层从后往前遍历 target 到当前元素值避免重复选取同一元素，对每个 j 取不选当前元素保持 dp[j] 原值和选当前元素 dp[j - nums[i]] + nums[i] 的较大值更新 dp[j] ，过程中若发现 dp[target] 等于 target 则提前返回 true，若遍历结束未满足条件则返回 false。
具体代码：
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for (int i = 0; i < nums.size(); i++) sum += nums[i]; if (sum % 2) return false; int target = sum / 2; vector<int> dp(target + 1, 0); 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]); if (dp[target] == target) return true; } } return false; } };时间复杂度：O（n * target）
空间复杂度：O（target）
