理論基礎(chǔ)
01 背包
有n件物品和一個(gè)最多能背重量為w 的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大。
二維dp數(shù)組01背包
- 確定dp數(shù)組以及下標(biāo)的含義
是使用二維數(shù)組，即dp[i][j] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。
2.確定遞推公式
再回顧一下dp[i][j]的含義：從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。
那么可以有兩個(gè)方向推出來dp[i][j]，
- 不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價(jià)值，此時(shí)dp[i][j]就是dp[i - 1][j]。(其實(shí)就是當(dāng)物品i的重量大于背包j的重量時(shí)，物品i無法放進(jìn)背包中，所以背包內(nèi)的價(jià)值依然和前面相同。)
- 放物品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]，無論是選取哪些物品，背包價(jià)值總和一定為0
4.確定遍歷順序
先遍歷物品，然后遍歷背包重量
// weight數(shù)組的大小 就是物品個(gè)數(shù)
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ù)組
完整代碼
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];
}
// weight數(shù)組的大小 就是物品個(gè)數(shù)
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();
}
01背包理論基礎(chǔ)（滾動(dòng)數(shù)組）
倒序遍歷是為了保證物品i只被放入一次，把i的維度去掉了
從后往前循環(huán)，每次取得狀態(tài)不會(huì)和之前取得狀態(tài)重合，這樣每種物品就只取一次了。
不可以更換for循環(huán)的順序
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();
}
416. 分割等和子集
- 確定dp數(shù)組以及下標(biāo)的含義
dp[j]表示 背包總?cè)萘浚ㄋ苎b的總重量）是j，放進(jìn)物品后，背的最大重量為dp[j]。
2.確定遞推公式
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3.dp數(shù)組如何初始化
如果題目給的價(jià)值都是正整數(shù)那么非0下標(biāo)都初始化為0就可以了，如果題目給的價(jià)值有負(fù)數(shù)，那么非0下標(biāo)就要初始化為負(fù)無窮。
4.確定遍歷順序
使用一維dp數(shù)組，物品遍歷的for循環(huán)放在外層，遍歷背包的for循環(huán)放在內(nèi)層，且內(nèi)層for循環(huán)倒序遍歷
5.舉例推導(dǎo)dp數(shù)組
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
// dp[i]中的i表示背包內(nèi)總和
// 題目中說：每個(gè)數(shù)組中的元素不會(huì)超過 100，數(shù)組的大小不會(huì)超過 200
// 總和不會(huì)大于20000，背包最大只需要其中一半，所以10001大小就可以了
vector<int> dp(10001, 0);
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 也可以使用庫函數(shù)一步求和
// 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--) { // 每一個(gè)元素一定是不可重復(fù)放入，所以從大到小遍歷
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
// 集合中的元素正好可以湊成總和target
return dp[target] == target;
}
};
1049.最后一塊石頭的重量II
- 確定dp數(shù)組以及下標(biāo)的含義
dp[j]表示容量（其實(shí)就是重量）為j的背包，最多可以背最大重量為dp[j]
2.確定遞推公式
01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本題則是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
3.dp數(shù)組如何初始化
因?yàn)橹亓慷疾粫?huì)是負(fù)數(shù)，所以dp[j]都初始化為0就可以了
4.確定遍歷順序
如果使用一維dp數(shù)組，物品遍歷的for循環(huán)放在外層，遍歷背包的for循環(huán)放在內(nèi)層，且內(nèi)層for循環(huán)倒序遍歷！
5.舉例推導(dǎo)dp數(shù)組
//時(shí)間復(fù)雜度：O(m × n) , m是石頭總重量（準(zhǔn)確的說是總重量的一半），n為石頭塊數(shù)
//空間復(fù)雜度：O(m)
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(1501, 0);
int sum = 0;
for (int i = 0; i < stones.size(); i++) sum += stones[i];
int target = sum / 2;
for (int i = 0; i < stones.size(); i++) { // 遍歷物品
for (int j = target; j >= stones[i]; j--) { // 遍歷背包
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};
494.目標(biāo)和
既然為target，那么就一定有 left組合 - right組合 = target。
left + right = sum，而sum是固定的。right = sum - left
公式來了， left - (sum - left) = target 推導(dǎo)出 left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出來。
此時(shí)問題就是在集合nums中找出和為left的組合。
回溯法超時(shí)
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
}
// 如果 sum + candidates[i] > target 就終止遍歷
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i + 1);
sum -= candidates[i];
path.pop_back();
}
}
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (S > sum) return 0; // 此時(shí)沒有方案
if ((S + sum) % 2) return 0; // 此時(shí)沒有方案，兩個(gè)int相加的時(shí)候要各位小心數(shù)值溢出的問題
int bagSize = (S + sum) / 2; // 轉(zhuǎn)變?yōu)榻M合總和問題，bagsize就是要求的和
// 以下為回溯法代碼
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 需要排序
backtracking(nums, bagSize, 0, 0);
return result.size();
}
};
動(dòng)態(tài)規(guī)劃
x = (target + sum) / 2
此時(shí)問題就轉(zhuǎn)化為，裝滿容量為x的背包，有幾種方法。這里的x，就是bagSize
因?yàn)槊總€(gè)物品（題目中的1）只用一次！
這次和之前遇到的背包問題不一樣了，之前都是求容量為j的背包，最多能裝多少。
本題則是裝滿有幾種方法。其實(shí)這就是一個(gè)組合問題了。
- 確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[j]:填滿j（包括j）這么大容積的包，有dp[j]種方法
- 確定遞推公式
在求裝滿背包有幾種方法的情況下:dp[j]+=dp[j-nums[i]]
- dp數(shù)組如何初始化
如果數(shù)組[0] ，target = 0，那么 bagSize = (target + sum) / 2 = 0。 dp[0]也應(yīng)該是1， 也就是說給數(shù)組里的元素 0 前面無論放加法還是減法，都是 1 種方法
- 確定遍歷順序
nums放在外循環(huán)，target在內(nèi)循環(huán)，且內(nèi)循環(huán)倒序。
- 舉例推導(dǎo)dp數(shù)組
輸入：nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
//時(shí)間復(fù)雜度：O(n × m)，n為正數(shù)個(gè)數(shù)，m為背包容量
//空間復(fù)雜度：O(m)，m為背包容量
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(S) > sum) return 0; // 此時(shí)沒有方案
if ((S + sum) % 2 == 1) return 0; // 此時(shí)沒有方案
int bagSize = (S + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
474.一和零
01背包有兩個(gè)維度，一個(gè)是m 一個(gè)是n，而不同長度的字符串就是不同大小的待裝物品。
- 確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j]：最多有i個(gè)0和j個(gè)1的strs的最大子集的大小為dp[i][j]。
2.確定遞推公式
dp[i][j] 可以由前一個(gè)strs里的字符串推導(dǎo)出來，strs里的字符串有zeroNum個(gè)0，oneNum個(gè)1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我們在遍歷的過程中，取dp[i][j]的最大值。
所以遞推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
此時(shí)大家可以回想一下01背包的遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
對(duì)比一下就會(huì)發(fā)現(xiàn)，字符串的zeroNum和oneNum相當(dāng)于物品的重量（weight[i]），字符串本身的個(gè)數(shù)相當(dāng)于物品的價(jià)值（value[i]）
3.dp數(shù)組如何初始化
因?yàn)槲锲穬r(jià)值不會(huì)是負(fù)數(shù)，初始為0
4.確定遍歷順序
外層for循環(huán)遍歷物品，內(nèi)層for循環(huán)遍歷背包容量且從后向前遍歷！文章來源：http://www.zghlxwxcb.cn/news/detail-469554.html
for (string str : strs) { // 遍歷物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍歷背包容量且從后向前遍歷！
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
遍歷背包容量的兩層for循環(huán)先后循序沒講究，都是物品重量的一個(gè)維度，先遍歷哪個(gè)都行！
文章來源地址http://www.zghlxwxcb.cn/news/detail-469554.html
//時(shí)間復(fù)雜度: O(kmn)，k 為strs的長度
//空間復(fù)雜度: O(mn)
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默認(rèn)初始化0
for (string str : strs) { // 遍歷物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
for (int i = m; i >= zeroNum; i--) { // 遍歷背包容量且從后向前遍歷！
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃01背包問題-代碼隨想錄-刷題筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
