【代码随想录】day42

本文主要是介绍【代码随想录】day42，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

一、01背包问题理论基础

1.不同背包的区别：

• 0-1背包：有n种物品，每种只有1个
• 完全背包：有n种物品，每种有无限个
• 多重背包：有n种物品，每种物品的个数各不相同

2.0-1背包原理

dp[i][j]的含义：[0, i]的物品，任取，放入容量为j的背包
不放物品i，最大价值：dp[i-1][j]
放物品i，最大价值：dp[i-1][j-weight[i]] + value[i]
递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

3.滚动数组压缩二维dp数组

dp[j]的含义：容量为j的背包能放的最大价值
递推公式：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
遍历顺序：
先遍历物品，再遍历背包，背包重量倒叙（因为不能先修改前面的值，需要用到）

for (int i = 0; i < 物品数量; i ++) {for (int j = bagweight; j >= weight[i]; j --) {递推公式;}
}

二、416分割等和子集

二维dp：

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

一维dp：

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

---

这篇关于【代码随想录】day42的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---