動(dòng)態(tài)規(guī)劃理論基礎(chǔ)
動(dòng)規(guī)五部曲：
- 確定dp數(shù)組 下標(biāo)及dp[i] 的含義。
- 遞推公式：比如斐波那契數(shù)列 dp[i] = dp[i-1] + dp[i-2]。
- 初始化dp數(shù)組。
- 確定遍歷順序：從前到后or其他。
- 推導(dǎo)dp數(shù)組。
出現(xiàn)結(jié)果不正確：
- 打印dp日志和自己想的一樣：遞推公式、初始化或者遍歷順序出錯(cuò)。
- 打印dp日志和自己想的不一樣：代碼實(shí)現(xiàn)細(xì)節(jié)出現(xiàn)問題。
416. 分割等和子集
參考文檔：代碼隨想錄
題目：
給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
注意: 每個(gè)數(shù)組中的元素不會超過 100 數(shù)組的大小不會超過 200
- 示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].- 示例 2:
輸入: [1, 2, 3, 5]
輸出: false
解釋: 數(shù)組不能分割成兩個(gè)元素和相等的子集.- 提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
分析：
dp五部曲：
- dp[j]含義：背包重量為i時(shí)候可以裝最大價(jià)值數(shù)。
- 遞推公式：dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
- 初始化：vector<int> dp(total+1, 0); 不能影響dp[j]的更新，設(shè)為最小自然數(shù)0。
- 遍歷順序：雙重for循環(huán)，先物品再背包，內(nèi)層for循環(huán)的循環(huán)體 倒序 更新dp，適應(yīng)滾動(dòng)數(shù)組，不影響之前的更新，正序因?yàn)橹挥幸粋€(gè)一維數(shù)組，所以會影響后面的更新。
- 打印：
輸入: [1, 5, 11, 5]
dp更新：
下標(biāo)值：0，1，2，3，4，5，6，7，8，9，10，11
初始化：0，0，0，0，0，0，0，0，0，0，0，0
i = 0 ：0，1，1，1，1，1，1，1，1，1，1，1
i = 1 ：0，1，1，1，1，5，6，6，6，6，6，6
i = 2 ：0，1，1，1，1，5，6，6，6，6，6，11
i = 3 ：0，1，1，1，1，5，6，6，6，6，10，11
代碼：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = 0;
for(int i = 0; i < nums.size(); i++){
total += nums[i];
}
if(total % 2) return false;
total /= 2;// 背包的目標(biāo)體積
vector<int> dp(total+1, 0);
for(int i = 0; i < nums.size(); i++){//物品個(gè)數(shù)0-nums.size()-1
for(int j = total; j >= nums[i]; j--){//背包的體積0-total
dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]); //遞推公式
}
}
if(dp[total] == total) return true;
return false;
}
};
二維數(shù)組實(shí)現(xiàn)：
- dp[i][j]含義：從0-i的物品中任取到重量限制為j的背包得到的最大價(jià)值數(shù)。
- 遞推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
- 初始化：vector<vector<int>> dp(nums.size(), vector<int>(total+1, 0)); 第一列表示背包的重量為0時(shí)的價(jià)值為0，第一行表示在物品0存在的情況下背包不同重量的價(jià)值，滿足條件的初始化為物品0的價(jià)值，其他元素都需要之后從上和左上的二維數(shù)組元素值計(jì)算得出，所以初始化值任意。
- 遍歷順序：雙重for循環(huán)，對于二維數(shù)組，先物品再背包或者先背包再物品，在當(dāng)前額日偽數(shù)組求最大價(jià)值的時(shí)候上和左上元素都是存在的，所以遍歷順序任意。
先物品再背包文章來源：http://www.zghlxwxcb.cn/news/detail-828766.html
class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = 0;
for(int i = 0; i < nums.size(); i++){
total += nums[i];
}
if(total % 2) return false;
total /= 2;// 背包的目標(biāo)體積
//二維數(shù)組
vector<vector<int>> dp(nums.size(), vector<int>(total+1, 0));
for(int i = total; i >= nums[0]; i--) dp[0][i] = nums[0];
for(int i = 1; i < nums.size(); i++){//先物品
for(int j = 1; j <= total; j++){//再背包
if(j < nums[i]) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i]);
}
}
if(dp[nums.size()-1][total] == total) return true;
return false;
}
};
先背包再物品文章來源地址http://www.zghlxwxcb.cn/news/detail-828766.html
class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = 0;
for(int i = 0; i < nums.size(); i++){
total += nums[i];
}
if(total % 2) return false;
total /= 2;// 背包的目標(biāo)體積
//二維數(shù)組
vector<vector<int>> dp(nums.size(), vector<int>(total+1, 0));
for(int i = total; i >= nums[0]; i--) dp[0][i] = nums[0];
for(int j = 1; j <= total; j++){//先背包
for(int i = 1; i < nums.size(); i++){//再物品
if(j < nums[i]) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i]);
}
}
if(dp[nums.size()-1][total] == total) return true;
return false;
}
};
到了這里，關(guān)于【Day42】代碼隨想錄之動(dòng)態(tài)規(guī)劃0-1背包_416. 分割等和子集的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
