代碼隨想錄算法訓練營第三十天 | 卡碼網46.攜帶研究材料（二維解法）、卡碼網46.攜帶研究材料（滾動數組）、LeetCode416.分割等和子集

01-1 卡碼網46.攜帶研究材料（二維）

相關資源

題目鏈接：46. 攜帶研究材料

文章講解：01背包二維問題

視頻講解：0-1背包問題

題目：

小明是一位科學家，他需要參加一場重要的國際科學大會，以展示自己的最新研究成果。他需要帶一些研究材料，但是他的行李箱空間有限。這些研究材料包括實驗設備、文獻資料和實驗樣本等等，它們各自占據不同的空間，并且具有不同的價值。

小明的行李空間為 N，問小明應該如何抉擇，才能攜帶最大價值的研究材料，每種研究材料只能選擇一次，并且只有選與不選兩種選擇，不能進行切割。

第一想法：我之前是接觸過01背包問題的，但現在一點思路也沒有

看完代碼隨想錄之后的想法：

五部曲

dp數組的含義：dp[i][j]表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少
確定遞推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
初始化dp數組，dp[i][0]=0,當 j < weight[0]的時候，dp[0][j] 是 0，因為背包容量比編號0的物品重量還小。當j >= weight[0]時，dp[0][j]應該是value[0]，因為背包容量放足夠放編號0物品。
確定遍歷順序，先遍歷物品和先遍歷背包重量都可以，因為均由左上角推導得到
打印dp數組

實現：

#include <bits/stdc++.h>
using namespace std;int main() {int n, bagweight;// bagweight代表行李箱空間cin >> n >> bagweight;vector<int> weight(n, 0); // 存儲每件物品所占空間vector<int> value(n, 0);  // 存儲每件物品價值for(int i = 0; i < n; ++i) {cin >> weight[i];}for(int j = 0; j < n; ++j) {cin >> value[j];}// dp數組, dp[i][j]代表行李箱空間為j的情況下,從下標為[0, i]的物品里面任意取,能達到的最大價值vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化, 因為需要用到dp[i - 1]的值// j < weight[0]已在上方被初始化為0// j >= weight[0]的值就初始化為value[0]for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}for(int i = 1; i < weight.size(); i++) { // 遍歷科研物品for(int j = 0; j <= bagweight; j++) { // 遍歷行李箱容量if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果裝不下這個物品,那么就繼承dp[i - 1][j]的值else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}cout << dp[n - 1][bagweight] << endl;return 0;
}

ToDo：自己寫出來

2025-3-3：

#include <bits/stdc++.h>
using namespace std;
int main(){int M, 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 j = 0; j < M; j++){cin >> value[j];}// 初始化vector<vector<int>> dp(weight.size(),vector<int>(N+1,0));for(int j = weight[0]; j<= N; j++){dp[0][j] = 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] << endl;
}

01-2 卡碼網46.攜帶研究材料（一維）

相關資源

題目鏈接：46. 攜帶研究材料

文章講解：01背包問題一維

視頻講解：01背包問題（滾動數組篇）

題目：

小明的行李空間為 N，問小明應該如何抉擇，才能攜帶最大價值的研究材料，每種研究材料只能選擇一次，并且只有選與不選兩種選擇，不能進行切割。

看完代碼隨想錄之后的想法：

五部曲

dp數組的含義：dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]
確定遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
初始化dp數組，dp數組初始化的時候，都初始為0就可以了
確定遍歷順序，先遍歷物品再遍歷背包重量，并且要求背包容量由大到小遍歷，從而保證物品i只被放入一次
打印數組

實現：

// 一維dp數組實現
#include <iostream>
#include <vector>
using namespace std;int main() {// 讀取 M 和 Nint M, N;cin >> M >> N;vector<int> costs(M);vector<int> values(M);for (int i = 0; i < M; i++) {cin >> costs[i];}for (int j = 0; j < M; j++) {cin >> values[j];}// 創建一個動態規劃數組dp，初始值為0vector<int> dp(N + 1, 0);// 外層循環遍歷每個類型的研究材料for (int i = 0; i < M; ++i) {// 內層循環從 N 空間逐漸減少到當前研究材料所占空間for (int j = N; j >= costs[i]; --j) {// 考慮當前研究材料選擇和不選擇的情況，選擇最大值dp[j] = max(dp[j], dp[j - costs[i]] + values[i]);}}// 輸出dp[N]，即在給定 N 行李空間可以攜帶的研究材料最大價值cout << dp[N] << endl;return 0;
}

ToDo：復刻

2025-3-3：

#include <bits/stdc++.h>
using namespace std;
int main(){int M, 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 j = 0; j < M; j++){cin >> value[j];}// 初始化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] << endl;
}

感悟：其實從前往后還是從后往前遍歷很好想，二維遍歷過程可以發現，當前的dp[i][j] 來自于上方正對和上方偏左，如果一維滾動數組從前往后遍歷，前面的發生改變，后面的就會被影響；至于為什么先遍歷物品，再遍歷背包容量，假如順序顛倒過來，其實可以還原成二維遍歷過程，因為二維遍歷的從上往下再從左往右，當前單元格其實是用到了當前單元格的上一個單元格，并不能豎著拷貝（要想這樣，除非dp[i][j] = max(dp[i][j-1], dp[i - weight[j]+value[j]][j - 1)，換句話說i和j是不可對調等價的）

01-3 LeetCode416.分割等和子集

相關資源

題目鏈接：416. 分割等和子集

文章講解：分割等和子集

視頻講解：LeetCode：416.分割等和子集

題目：

給你一個 只包含正整數 的非空數組 nums 。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

第一想法：這個想不出來和01背包有關系

看完代碼隨想錄之后的想法：

問題轉化：

首先，本題要求集合里能否出現總和為 sum / 2 的子集。既有一個只能裝重量為 sum / 2 的背包，商品為數字，這些數字能不能把這個背包裝滿。那每一件商品是數字的話，對應的重量和價值是多少呢？一個數字只有一個維度，即重量等于價值。當數字可以裝滿承載重量為 sum / 2 的背包的背包時，這個背包的價值也是 sum / 2。那么這道題就是裝滿承載重量為 sum / 2 的背包，價值最大是多少？如果最大價值是 sum / 2，說明正好被商品裝滿了

動規五部曲分析如下：

確定dp數組以及下標的含義：01背包中，dp[j] 表示：容量（所能裝的重量）為j的背包，所背的物品價值最大可以為dp[j]
確定遞推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
初始化：為0
遍歷順序：一維dp數組，物品遍歷的for循環放在外層，遍歷背包的for循環放在內層，且內層for循環倒序遍歷
打印數組

實現：

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

收獲：題目中物品是nums[i]，重量是nums[i]，價值也是nums[i]，背包體積是sum/2。

ToDo：復現