刷題的第二十九天，希望自己能夠不斷堅(jiān)持下去，迎來(lái)蛻變。😀😀😀
刷題語(yǔ)言：C++
Day29 任務(wù)
● 01背包問(wèn)題，你該了解這些！
● 01背包問(wèn)題，你該了解這些！ 滾動(dòng)數(shù)組
● 416. 分割等和子集

1 動(dòng)態(tài)規(guī)劃：01背包問(wèn)題，你該了解這些！

背包問(wèn)題的理論基礎(chǔ)重中之重是01背包

1.1 01 背包

01 背包：有n件物品和一個(gè)最多能背重量為w的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i]。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大

	重量	價(jià)值
物品0	1	15
物品1	3	20
物品2	4	30

二維dp數(shù)組01背包
（1）確定dp數(shù)組以及下標(biāo)的含義
dp[i][j] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。

（2）確定遞推公式

1.不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價(jià)值，此時(shí)dp[i][j]就是dp[i - 1][j]。(其實(shí)就是當(dāng)物品i的重量大于背包j的重量時(shí)，物品i無(wú)法放進(jìn)背包中，所以背包內(nèi)的價(jià)值依然和前面相同。)
2.放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時(shí)候不放物品i的最大價(jià)值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價(jià)值），就是背包放物品i得到的最大價(jià)值

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

（3）dp數(shù)組如何初始化

首先從dp[i][j]的定義出發(fā)，如果背包容量j為0的話，即dp[i][0]，無(wú)論是選取哪些物品，背包價(jià)值總和一定為0。如圖：

狀態(tài)轉(zhuǎn)移方程是由 i-1 推導(dǎo)出來(lái)，那么i為0的時(shí)候就一定要初始化
dp[0][j]，即：i為0，存放編號(hào)0的物品的時(shí)候，各個(gè)容量的背包所能存放的最大價(jià)值。

那么很明顯當(dāng) j < weight[0]的時(shí)候，dp[0][j] 應(yīng)該是 0，因?yàn)楸嘲萘勘染幪?hào)0的物品重量還小。
當(dāng)j >= weight[0]時(shí)，dp[0][j] 應(yīng)該是value[0]，因?yàn)楸嘲萘糠抛銐蚍啪幪?hào)0物品

for (int j = 0; j < weight[0]; j++) {dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

dp[0][j] 和 dp[i][0] 都已經(jīng)初始化，其他下標(biāo)的初始化什么數(shù)值都可以，因?yàn)槎紩?huì)被覆蓋。

vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

（4）遍歷順序

先遍歷物品，然后遍歷背包重量

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];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

先遍歷背包，再遍歷物品

// weight數(shù)組的大小 就是物品個(gè)數(shù)
for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量for(int i = 1; i < weight.size(); i++) { // 遍歷物品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]);}
}

（5）舉例推導(dǎo)dp數(shù)組

C++：

void test_2_wei_bag_problem1() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagweight = 4;// 二維數(shù)組vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 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];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() {test_2_wei_bag_problem1();
}

2 動(dòng)態(tài)規(guī)劃：01背包理論基礎(chǔ)（滾動(dòng)數(shù)組）

背包最大重量為4。

物品為：

	重量	價(jià)值
物品0	1	15
物品1	3	20
物品2	4	30

一維dp數(shù)組：上一層可以重復(fù)利用，直接拷貝到當(dāng)前層。
dp[i][j] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。
（1）確定dp數(shù)組的定義
dp[j]表示：容量為j的背包，所背的物品價(jià)值可以最大為dp[j]
（2）一維dp數(shù)組的遞推公式

dp[j]有兩個(gè)選擇，一個(gè)是取自己dp[j] 相當(dāng)于 二維dp數(shù)組中的dp[i-1][j]，即不放物品i，一個(gè)是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，畢竟是求最大價(jià)值

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

（3）一維dp數(shù)組如何初始化
假設(shè)物品價(jià)值都是大于0的，所以dp數(shù)組初始化的時(shí)候，都初始為0
（4）一維dp數(shù)組遍歷順序

for (int i = 0; i < weight.size(); i++) {// 遍歷物品for (int j = bagweight; j >= weight[i]; j--) {// 遍歷背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}

倒序遍歷是為了保證物品i只被放入一次！ 如果一旦正序遍歷了，那么物品0就會(huì)被重復(fù)加入多次！

為什么二維dp數(shù)組遍歷的時(shí)候不用倒序呢？
因?yàn)閷?duì)于二維dp，dp[i][j]都是通過(guò)上一層即dp[i - 1][j]計(jì)算而來(lái)，本層的dp[i][j]并不會(huì)被覆蓋！

（5）舉例推導(dǎo)dp數(shù)組

C++：

void test_1_wei_bag_problem() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagWeight = 4;// 初始化vector<int> dp(bagWeight + 1, 0);for(int i = 0; i < weight.size(); i++) { // 遍歷物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;
}int main() {test_1_wei_bag_problem();
}

3 分割等和子集

416. 分割等和子集

思路：
背包問(wèn)題，有N件物品和一個(gè)最多能背重量為W 的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大。

本題使用的是01背包，因?yàn)樵匚覀冎荒苡靡淮巍?br /> 把01背包問(wèn)題套到本題：
（1）背包的體積為sum / 2
（2）背包要放入的商品（集合里的元素）重量為 元素的數(shù)值，價(jià)值也為元素的數(shù)值
（3）背包如果正好裝滿，說(shuō)明找到了總和為 sum / 2 的子集。
（4）背包中每一個(gè)元素是不可重復(fù)放入。

動(dòng)態(tài)規(guī)劃
（1）確定dp數(shù)組以及下標(biāo)的含義
01背包中，dp[j] 表示： 容量為j的背包，所背的物品價(jià)值最大可以為dp[j]
本題：dp[j]表示 背包總?cè)萘?#xff08;所能裝的總重量）是j，放進(jìn)物品后，背的最大重量為dp[j]
（2）確定遞推公式

01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本題，相當(dāng)于背包里放入數(shù)值，那么物品i的重量是nums[i]，其價(jià)值也是nums[i]。
所以遞推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

（3）dp數(shù)組如何初始化

dp[0]一定是0。
如果題目給的價(jià)值都是正整數(shù)那么非0下標(biāo)都初始化為0就可以了，如果題目給的價(jià)值有負(fù)數(shù)，那么非0下標(biāo)就要初始化為負(fù)無(wú)窮。
這樣才能讓dp數(shù)組在遞推的過(guò)程中取得最大的價(jià)值，而不是被初始值覆蓋了

（4）確定遍歷順序

for (int i = 0; i < nums.size(); i++) {for (int j = target; j >= nums[i]; j--) {// 每一個(gè)元素一定是不可重復(fù)放入，所以從大到小遍歷dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}
}

（5）舉例推導(dǎo)dp數(shù)組
dp[j]的數(shù)值一定是小于等于j的,如果dp[j] == j 說(shuō)明，集合中的子集總和正好可以湊成總和j

C++：

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;vector<int> dp(10001, 0);for (int i = 0; i < nums.size(); i++) {sum += nums[i];}if (sum % 2 == 1) return false;int target = sum / 2;// 開(kāi)始 01背包for(int i = 0; i < nums.size(); i++) {for(int j = target; j >= nums[i]; j--) { // 每一個(gè)元素一定是不可重復(fù)放入，所以從大到小遍歷dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}// 集合中的元素正好可以湊成總和targetif (dp[target] == target) return true;return false;}
};

時(shí)間復(fù)雜度：$O(n^2)$
空間復(fù)雜度：$O(n)$，雖然dp數(shù)組大小為一個(gè)常數(shù)，但是大常數(shù)

---

鼓勵(lì)堅(jiān)持三十天的自己😀😀😀