文章目录
- 1049.最后一块石头的重量II
- 494.目标和
- 474.一和零
1049.最后一块石头的重量II
题目链接
文章讲解
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 1. 确定 DP 数组及下标的含义：// dp[i][j] 表示考虑前 i 块石头，是否能够通过选择一部分石头，凑出总和为 j。// 具体地，dp[i][j] 表示使用前 i 块石头，是否可以组合出和为 j 的子集。// 我们的目标是计算 dp 数组，并在最后返回最后两块石头的差值。int sum = 0;// 2. 计算所有元素的总和：// sum 是数组 stones 所有元素的和。我们需要判断是否可以将数组分成两个子集，// 每个子集的和应该是 sum / 2。for (auto stone : stones) {sum += stone; // 累加所有石头的重量}int ans = sum / 2; // 目标和是 sum / 2，目的是将石头的总和分成两个部分，每个子集的和为 ansint m = stones.size();// 3. DP 数组如何初始化：// dp 数组是一个二维数组，dp[i][j] 表示考虑前 i 块石头，是否可以达到重量 j。// dp 数组的大小是 m 行，ans + 1 列，默认值初始化为 0。vector<vector<int>> dp(m, vector<int>(ans + 1, 0));// 4. 初始化 dp 数组：// 对于第 0 块石头，可以用它来构造和为其重量的子集。for (int i = stones[0]; i <= ans; i++) {dp[0][i] = stones[0]; // 如果重量大于等于 stones[0]，则可以用第一个石头构成和为 stones[0] 的子集}// 5. 填充 DP 数组：// 遍历剩下的每块石头，更新 dp 数组。选择是否将当前石头添加到子集，或者跳过该石头。for (int i = 1; i < m; i++) { // 遍历所有石头for (int j = 0; j <= ans; j++) { // 遍历每个目标重量if (j < stones[i]) {dp[i][j] = dp[i - 1][j]; // 如果当前重量 j 小于石头的重量，则继承前一块石头的值} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]); // 否则，选择当前石头}}}// 6. 最终结果：// dp[m-1][ans] 表示使用所有石头，能否凑出和为 ans 的子集。// 计算剩余的石头差值，返回最终的差值。int x = sum - dp[m - 1][ans]; // 计算剩余部分的和return x - dp[m - 1][ans]; // 返回最后两块石头的差值}
};494.目标和
题目链接
文章讲解
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// 1. 确定 DP 数组及下标的含义：// dp[j] 表示是否能通过选择一部分数，使得它们的总和为 j。// dp[bagSize] 代表是否可以通过选择一些数的加减法得到总和为 bagSize（即 (sum + target) / 2）。int sum = 0;// 2. 计算所有元素的总和：// sum 是数组 nums 所有元素的和。我们需要将目标 target 转换成一个可以用背包问题解决的子问题。for (auto num : nums) {sum += num; // 累加所有元素的和}// bagSize 是我们背包的容量，其计算公式为 (sum + target) / 2。// 这是因为将一个数分为加和与减和两部分，最终的目标是通过选取某些数使其总和为 bagSize。int bagSize = (sum + target) / 2;// 如果 (sum + target) 不是偶数，则不可能找到合适的分配方式if ((sum + target) % 2 == 1) return 0;// 如果目标的绝对值大于 sum，则不可能通过加减组合得到目标值if (abs(target) > sum) return 0;// 3. DP 数组如何初始化：// dp 数组的大小为 bagSize + 1，初始化为 0。dp[0] = 1 表示和为 0 的子集是空集，可以成立。vector<int> dp(bagSize + 1, 0);dp[0] = 1; // 和为 0 的子集是空集// 4. 确定递推公式：// dp[j] = dp[j] + dp[j - nums[i]]// dp[j] 表示当前和为 j 的子集数目，dp[j - nums[i]] 表示通过当前元素 nums[i] 可以组合出 j 的方式。// 我们从后向前遍历 dp 数组，防止重复使用同一元素。for (int i = 0; i < nums.size(); i++) { // 遍历每个元素for (int j = bagSize; j >= nums[i]; j--) { // 从 bagSize 向下遍历到 nums[i]dp[j] += dp[j - nums[i]]; // 当前重量 j 可以通过加入 nums[i] 来更新子集数目}}// 5. 最终结果：// dp[bagSize] 表示能否找到若干数的加和，使得其总和为 bagSize。返回 dp[bagSize] 即可。return dp[bagSize];}
};474.一和零
题目链接
文章讲解
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// 1. 确定 DP 数组及下标的含义：// dp[i][j] 表示我们在使用最多 i 个 '0' 和 j 个 '1' 的情况下，能组成的最大字符串个数。// dp[m][n] 代表我们可以使用最多 m 个 '0' 和 n 个 '1' 的情况下，能够构成的最大子集数。vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化 DP 数组dp[0][0] = 0; // 初始条件：使用 0 个 '0' 和 0 个 '1' 可以组成 0 个字符串// 2. 遍历每个字符串：// 对于每个字符串，我们计算它含有多少个 '0' 和 '1'，然后更新 DP 数组。for (auto str : strs) {int x = 0, y = 0;// 3. 计算当前字符串的 '0' 和 '1' 的个数：// 遍历当前字符串，统计其中 '0' 和 '1' 的数量。for (auto c : str) {if (c == '0') x++; // '0' 的数量else y++; // '1' 的数量}// 4. 更新 DP 数组：// 从后向前遍历，避免重复使用当前字符串for (int i = m; i >= x; i--) { // 遍历所有可能的 '0' 数量for (int j = n; j >= y; j--) { // 遍历所有可能的 '1' 数量dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1); // 当前字符串可以选择加入，更新 dp[i][j]}}}// 5. 最终结果：// 返回 dp[m][n]，即在使用最多 m 个 '0' 和 n 个 '1' 的情况下，能够构成的最大子集数。return dp[m][n];}
};纯 0 - 1 背包 (opens new window)是求 给定背包容量 装满背包 的最大价值是多少。
416. 分割等和子集 (opens new window)是求 给定背包容量，能不能装满这个背包。
1049. 最后一块石头的重量 II (opens new window)是求 给定背包容量，尽可能装，最多能装多少
494. 目标和 (opens new window)是求 给定背包容量，装满背包有多少种方法。
本题是求 给定背包容量，装满背包最多有多少个物品。
