打卡第42天，搞搞01背包。

今日任務(wù)

• 01背包問(wèn)題，你該了解這些！
• 01背包問(wèn)題，你該了解這些！ 滾動(dòng)數(shù)組
• 416.分割等和子集

背包問(wèn)題1.0 ：0-1 背包

01背包

輸入格式

第一行兩個(gè)整數(shù)，N，V，用空格隔開(kāi)，分別表示物品數(shù)量和背包容積。

接下來(lái)有 N 行，每行兩個(gè)整數(shù) $v_i$,$w_i$，用空格隔開(kāi)，分別表示第 i 件物品的體積和價(jià)值。

輸出格式

輸出一個(gè)整數(shù)，表示最大價(jià)值。

數(shù)據(jù)范圍

0<N,V≤1000

0<$v_i$,$w_i$≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5

輸出樣例：

8

代碼隨想錄

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

2. 確定遞推公式
   兩個(gè)方向推出來(lái)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無(wú)法放進(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[i][j]的定義出發(fā)，如果背包容量j為0的話，即dp[i][0]，無(wú)論是選取哪些物品，背包價(jià)值總和一定為0。

   狀態(tài)轉(zhuǎn)移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 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物品。

4. 確定遍歷順序
   二維數(shù)組的情況下 先遍歷背包跟先遍歷重量都可以
   一維數(shù)組的情況下 先遍歷重量

5. 推導(dǎo)
   

#include <bits/stdc++.h>using namespace std;int main() {int n, v;scanf("%d %d", &n, &v);vector<int> weight(n);vector<int> value(n);for(int i = 0; i < n; i++) {scanf("%d", &weight[i]);scanf("%d", &value[i]);}// 初始化vector<vector<int>> dp(n, vector<int>(v + 1, 0));for(int i = weight[0]; i <= v; i++) {dp[0][i] = value[0];}for(int i = 1; i < n; i++) {for(int j = 1; j <= v; j++) {if(j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);}}printf("%d", dp[n - 1][v]);return 0;
}

優(yōu)化空間（滾動(dòng)數(shù)組）

我們可以發(fā)現(xiàn)想知道dp[i][j] ，需要知道dp[i - 1][j - weight[i]] 和 dp[i - 1][j]，都只是前一層的信息，所以我們可以用一個(gè)一維數(shù)組來(lái)保存信息，只不過(guò)我們的遍歷順序第一次遍歷的是物品，第二層遍歷的是背包，而且是從大到小遍歷，因?yàn)橄胍来笾亓勘嘲淖畲髢r(jià)值總和，要知道前面的小重量背包的最大價(jià)值總和，而我們是用滾動(dòng)數(shù)組保存，如果從小到大遍歷，會(huì)改變小重量背包的最大價(jià)值總和。

#include <bits/stdc++.h>using namespace std;int main() {int n, v;scanf("%d %d", &n, &v);vector<int> weight(n);vector<int> value(n);for(int i = 0; i < n; i++) {scanf("%d", &weight[i]);scanf("%d", &value[i]);}// 初始化vector<int> dp(v + 1, 0);for(int i = weight[0]; i <= v; i++) {dp[i] = value[0];}for(int i = 1; i < n; i++) {for(int j = v; j >= 1; j--) {if(j < weight[i]) dp[j] = dp[j];else dp[j] = max(dp[j - weight[i]] + value[i], dp[j]);}}printf("%d", dp[v]);return 0;
}

416. 分割等和子集

輸入：nums = [1,5,11,5]
輸出：true
解釋：數(shù)組可以分割成 [1, 5, 5] 和 [11] 。

輸入：nums = [1,2,3,5]
輸出：false
解釋：數(shù)組不能分割成兩個(gè)元素和相等的子集。

我的題解

回溯暴力搜索，超時(shí)了哈哈哈

class Solution {
public:bool backtracking(vector<int>& nums, int sum, int starIndex) {if(sum == 0) return true;if(sum < 0) return false;for(int i = starIndex; i < nums.size(); i++) {sum -= nums[i];if(backtracking(nums, sum, i + 1)) return true;sum += nums[i];}return false;}bool canPartition(vector<int>& nums) {int sum = 0;for(int num : nums) sum += num;if(sum % 2 == 1) return false;sort(nums.begin(), nums.end());return backtracking(nums, sum / 2, 0);}
};

01背包做法，但是不是很理解。

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(int num : nums) sum += num;if(sum % 2 == 1) return false;vector<int> dp(sum / 2 + 1, 0);for(int i = nums[0]; i <= sum / 2; i++) dp[i] = nums[0]; // 初始化for(int i = 1; i < nums.size(); i++) {for(int j = sum / 2; j >= 1; j--) {if(j < nums[i]) dp[j] = dp[j];else dp[j] = max(dp[j - nums[i]] + nums[i], dp[j]);}}return dp[sum / 2] == sum / 2;}
};

代碼隨想錄

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;// dp[i]中的i表示背包內(nèi)總和// 題目中說(shuō)：每個(gè)數(shù)組中的元素不會(huì)超過(guò) 100，數(shù)組的大小不會(huì)超過(guò) 200// 總和不會(huì)大于20000，背包最大只需要其中一半，所以10001大小就可以了vector<int> dp(10001, 0);for (int i = 0; i < nums.size(); i++) {sum += nums[i];}// 也可以使用庫(kù)函數(shù)一步求和// int sum = accumulate(nums.begin(), nums.end(), 0);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ù)