w網(wǎng)站開(kāi)發(fā)文獻(xiàn)百度投訴中心在線申訴
刷題的第二十九天,希望自己能夠不斷堅(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 ) O(n^2) O(n2)
空間復(fù)雜度: O ( n ) O(n) O(n),雖然dp數(shù)組大小為一個(gè)常數(shù),但是大常數(shù)
鼓勵(lì)堅(jiān)持三十天的自己😀😀😀