算法训练营第三十四天（8.23）| 动态规划Part04：01背包

目录

Leecode 1049.最后一块石头的重量II

 Leecode 494.目标和

 Leecode 474.一和零

---

Leecode 1049.最后一块石头的重量II

题目地址：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目类型：01背包

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {// 背包的最大容量应当是 sum / 2 ，因为当两堆石头的重量最接近的时候mint sum = accumulate(stones.begin(), stones.end(), 0);int target = sum / 2;vector<int> dp(target + 1);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] * 2;}
};

 

 

 Leecode 494.目标和

题目地址：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目类型：01背包

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// sum = right + left// target = right - left// sum - target = 2left    int sum = accumulate(nums.begin(), nums.end(), 0);if ((sum - target) % 2 == 1 || abs(target) > sum) return 0; // left代表较少那一部分组合的和int left = (sum - target) / 2;// dp数组的含义是，当求和为i时，组合的数目vector<int> dp(left + 1);dp[0] = 1;for (int i = 0; i < nums.size(); ++i) {for (int j = left; j >= nums[i]; --j) {dp[j] += dp[j - nums[i]];}}return dp[left];}
};

 Leecode 474.一和零

题目地址：​​​​​​​力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目类型：01背包

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// 存储个数vector<pair<int, int>> nums;for (auto &it : strs) {int zero = 0, one = 0;for (auto &c : it) {if (c == '0') zero++;else one++;}nums.push_back({zero, one});}// dp[i][j]代表当有i个0，j个1时，最大的子集长度vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 先物品，后背包for (int k = 0; k < nums.size(); ++k) {// 二维for (int i = m; i >= nums[k].first; --i) {for (int j = n; j >= nums[k].second; --j) {// 注意，这里如果将第k个子集放进来，则代表增加一个子集，value是1，所以直接加1就行了dp[i][j] = max(dp[i][j], dp[i - nums[k].first][j - nums[k].second] + 1);}}}return dp[m][n];}
};

可以少一个循环，时间复杂度再降一下：

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {// dp[i][j]含义：当0的容量为i，1的容量为j时，子集的最大数目// 可知此时最大值问题，故考虑状态转移方程1vector<vector<int>> dp(m + 1, vector<int>(n + 1));for (int k = 0; k < strs.size(); ++k) {     // 遍历所有物品，即遍历所有子集int num0 = 0, num1 = 0;for (char c : strs[k]) {if (c == '0') num0++;else num1++;}for (int i = m; i >= num0; --i) {for (int j = n; j >= num1; --j) {dp[i][j] = max(dp[i][j], dp[i - num0][j - num1] + 1);}}}return dp[m][n];}
};