响应式网站模板企业,wordpress cms社交,ps个人网站设计总结,公司官网建设哪家好题目来源#xff1a;https://leetcode.cn/problems/partition-equal-subset-sum/description/ C题解#xff08;思路来源代码随想录#xff09; #xff1a;
背包问题有多种背包方式#xff0c;常见的有#xff1a;01背包、完全背包、多重背包、分组背包和混合背包等等。…题目来源https://leetcode.cn/problems/partition-equal-subset-sum/description/ C题解思路来源代码随想录
背包问题有多种背包方式常见的有01背包、完全背包、多重背包、分组背包和混合背包等等。一个商品如果可以重复多次放入是完全背包而只能放入一次是01背包本题中是01背包。
把01背包问题套到本题上来。
背包的体积为sum / 2背包要放入的商品集合里的元素重量为元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。
以上分析完我们就可以套用01背包来解决这个问题了。
确定dp数组以及下标的含义。二维数组: dp[i][j]表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。确定递推公式。两种情况不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值。所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i])。dp数组初始化。一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。状态转移方程可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。当 j weight[0]的时候dp[0][j] 应该是 0当j weight[0]时dp[0][j] 应该是value[0]。确定遍历顺序。有两个遍历的维度物品与背包重量。都可以 但是先遍历物品更好理解。举例推导dp数组。
class Solution {
public:bool canPartition(vectorint nums) {int len nums.size();int sum 0;for(int i 0; i len; i) {sum nums[i];}if(sum % 2 1) return false;vectorvectorint dp(len, vectorint(sum/21, 0));for(int ii nums[0]; ii sum/2; ii) {dp[0][ii] nums[0];}// 相当于包容量为sum/2在len个物品中挑选能装满则返回true。// 表示从0-j的元素中取出和小于k的最大值。for(int j 1; j len; j) {for(int k 0; k sum/2; k) {if(k nums[j]) dp[j][k] dp[j-1][k];else dp[j][k] max(dp[j-1][k], dp[j-1][k-nums[j]]nums[j]);}}if(dp[len-1][sum/2] sum/2) return true;else return false;}
};
# 使用一维dp数组滚动数组
在使用二维数组的时候递推公式dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上表达式完全可以是dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上不如只用一个一维数组了只用dp[j]一维数组也可以理解是一个滚动数组。这就是滚动数组的由来需要满足的条件是上一层可以重复利用直接拷贝到当前层。
在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。
注意遍历顺序必须先遍历物品再遍历包容量且更新内层for循环需要递减从后往前因为滚动数组的更新需要用到未更新的前面元素如果是递增从前往后前面更新的元素会影响后面的元素。
class Solution {
public:bool canPartition(vectorint nums) {int sum 0;// dp[i]中的i表示背包内总和// 题目中说每个数组中的元素不会超过 100数组的大小不会超过 200// 总和不会大于20000背包最大只需要其中一半所以10001大小就可以了vectorint dp(10001, 0);for (int i 0; i nums.size(); i) {sum nums[i];}// 也可以使用库函数一步求和// 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--) { // 每一个元素一定是不可重复放入所以从大到小遍历dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}// 集合中的元素正好可以凑成总和targetif (dp[target] target) return true;return false;}
};
