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)是求 給定背包容量，裝滿背包有多少種方法。
本題是求 給定背包容量，裝滿背包最多有多少個物品。