以下是今日份的總結

46 攜帶研究材料(二維數組)
46 攜帶研究材料(滾動數組/一維)
416 分割等和子集

今天的題目難度不低，掌握技巧了就會很簡單，盡量還是寫一些簡潔代碼 ^?_?^

攜帶研究材料(二維數組)

思路：

1.確定dp數組以及下標的含義
------ dp[i][j] 表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。
2.確定遞推公式
------不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價值，此時dp[i][j]就是dp[i - 1][j]。(其實就是當物品i的重量大于背包j的重量時，物品i無法放進背包中，所以背包內的價值依然和前面相同。)
------放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時候不放物品i的最大價值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值
------遞歸公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.dp數組如何初始化
------dp[0][j]，即：i為0，存放編號0的物品的時候，各個容量的背包所能存放的最大價值。
------那么很明顯當 j < weight[0]的時候，dp[0][j] 應該是 0，因為背包容量比編號0的物品重量還小。
------當j >= weight[0]時，dp[0][j] 應該是value[0]，因為背包容量放足夠放編號0物品。
------dp[i][j] 是由左上方數值推導出來了，那么 其他下標初始為什么數值都可以，因為都會被覆蓋。
------統一把dp數組統一初始為0，更方便一些。
4.確定遍歷順序
------先遍歷 物品還是先遍歷背包重量呢？
------其實都可以！！ 但是先遍歷物品更好理解。
5.舉例推導dp數組
------。。。。。。

值得注意的是

背包問題里，兩個for循環的先后循序是非常有講究；
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
遞歸公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推導出來的。

//二維dp數組實現
#include <bits/stdc++.h>
using namespace std;int n, bagweight;// bagweight代表行李箱空間
void solve() {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++) { // 遍歷行李箱容量// 如果裝不下這個物品,那么就繼承dp[i - 1][j]的值if (j < weight[i]) dp[i][j] = dp[i - 1][j];// 如果能裝下,就將值更新為 不裝這個物品的最大值 和 裝這個物品的最大值 中的 最大值// 裝這個物品的最大值由容量為j - weight[i]的包任意放入序號為[0, i - 1]的最大值 + 該物品的價值構成else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}cout << dp[weight.size() - 1][bagweight] << endl;
}int main() {while(cin >> n >> bagweight) {solve();}return 0;
}

攜帶研究材料(滾動數組/一維)

思路：

和上一題表現形式差不多
1.確定dp數組以及下標的含義
------ 在一維dp數組中，dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]。
_
2.確定遞推公式
------dp[j - weight[i]]表示容量為j - weight[i]的背包所背的最大價值。
------dp[j - weight[i]] + value[i] 表示 容量為 j - 物品i重量 的背包 加上 物品i的價值。（也就是容量為j的背包，放入物品i了之后的價值即：dp[j]）
------dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
_
3.dp數組如何初始化
------如果題目給的價值都是正整數那么非0下標都初始化為0就可以了
------dp[0]就應該是0，因為背包容量為0所背的物品的最大價值就是0。
_
4.確定遍歷順序
------如果使用一維dp數組，物品遍歷的for循環放在外層，遍歷背包的for循環放在內層，且內層for循環倒序遍歷！
------倒序遍歷是為了保證物品i只被放入一次！
_
5.舉例推導dp數組
------一維dp，分別用物品0，物品1，物品2 來遍歷背包

值得注意的是

一維dp數組的寫法，比較直觀簡潔，而且空間復雜度還降了一個數量級！

// 一維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;
}

分割等和子集

思路：

1.確定dp數組以及下標的含義
------ dp[j]表示 背包總容量（所能裝的總重量）是j，放進物品后，背的最大重量為dp[j]
2.確定遞推公式
------01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
------本題，相當于背包里放入數值，那么物品i的重量是nums[i]，其價值也是nums[i]。
------所以遞推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3.dp數組如何初始化
------從dp[j]的定義來看，首先dp[0]一定是0；
------如果題目給的價值都是正整數那么非0下標都初始化為0就可以了；
------如果題目給的價值有負數，那么非0下標就要初始化為負無窮；
------這樣才能讓dp數組在遞推的過程中取得最大的價值，而不是被初始值覆蓋了。
4.確定遍歷順序
------如果使用一維dp數組，物品遍歷的for循環放在外層，遍歷背包的for循環放在內層，且內層for循環倒序遍歷！
5.舉例推導dp數組
------dp[j]的數值一定是小于等于j的。
------如果dp[j] == j 說明，集合中的子集總和正好可以湊成總和j，理解這一點很重要。

值得注意的是

01背包相對于本題，主要要理解，題目中物品是nums[i]，重量是nums[i]，價值也是nums[i]，背包體積是sum/2。
如果使用一維dp數組，物品遍歷的for循環放在外層，遍歷背包的for循環放在內層，且內層for循環倒序遍歷！（很重要！！！）

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

寫在最后

----OK，今日份的博客就寫到這里，這一期的動態規劃好巧妙，明天繼續加油！！！
—還沒看下期的題，但是我的棧還有一節沒寫；
–追上時間進度了！！（笑
-🈚?。