代码随想录算法训练营第三十五天| 携带研究材料（01背包）、416. 分割等和子集

01背包问题是动态规划中的经典问题，其核心在于在有限的背包容量下选择物品以最大化价值。以下是对01背包问题的详细解析，包括二维和一维动态规划的实现方法，以及其在416. 分割等和子集问题中的应用。01背包问题二维动态规划状态定义：dp[i][j]表示在前i件物品中选择，且背包容量不超过j时能获得的最大价值。状态转移：不选第i件物品：dp[i][j] = dp[i-1][j]选第i件物品（前提是j = w[i]）：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])初始化：当容量j=0时，dp[i][0] = 0。当没有物品时（i=0），所有dp[0][j] = 0。填表顺序：外层循环物品i，内层循环容量j，逐个填充DP表。结果：dp[m][n]即为在m件物品中选择，背包容量不超过n的最大价值。一维动态规划（滚动数组优化）降维思路：用一维数组dp[j]来表示容量为j时的最大价值。更新顺序：从大到小遍历容量，确保每个物品只被用一次。状态转移：for (int j = W; j = weight[i]; j--) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}倒序遍历的原因：避免同一物品被重复计算，保证每个物品只用一次。416. 分割等和子集问题转化目标：将数组分成两个子集，使得两个子集的和相等。转化：判断能否从数组中挑出一部分数，使得它们的和等于sum(nums)/2。特殊情况处理：如果总和是奇数，直接返回false。背包模型背包容量：target = sum(nums)/2。物品：每个元素num看作一个物品，重量和价值均为num。问题：能否用这些物品恰好装满容量为target的背包。动态规划定义定义：dp[j]表示容量为j时，是否能被若干个数填满。初始化：dp[0] = true（背包容量0一定能装满）。状态转移遍历每个数：倒序遍历j从target到num：dp[j] = dp[j] || dp[j - num];解释：要么不用当前数，维持原状；要么用当前数，看能不能填满j-num。最终结果判断：看dp[target]是否为true。代码实现01背包问题（一维DP）#include iostream#include vectorusing namespace std;int main() { int m, n; scanf("%d%d", &m, &n); vectorint space(m + 1); vectorint value(m + 1); for (int i = 1; i = m; i++) scanf("%d", &space[i]); for (int i = 1; i = m; i++) scanf("%d", &value[i]); vectorint dp(n + 1, 0); for (int i = 1; i = m; i++) { for (int j = n; j = space[i]; j--) { dp[j] = max(dp[j], dp[j - space[i]] + value[i]); } } cout dp[n] endl; return 0;}416. 分割等和子集class Solution {public: bool canPartition(vectorint& nums) { if (nums.size() == 1) return false; int sum = 0; for (int num : nums) sum += num; if (sum % 2) return false; int target = sum / 2; vectorbool dp(target + 1, false); dp[0] = true; for (int num : nums) { if (num target) return false; for (int j = target; j = num; j--) { dp[j] = dp[j] || dp[j - num]; } if (dp[target]) return true; } return dp[target]; }};复杂度分