付网站建设费用会计分录,wordpress如何建立论坛,网站开发硬件环境怎么填,新网站如何做百度收录题目链接#xff1a;416. 分割等和子集
文章讲解#xff1a;代码随想录 416. 分割等和子集讲解
视频讲解#xff1a;动态规划之背包问题#xff0c;这个包能装满吗#xff1f;| LeetCode#xff1a;416.分割等和子集
思路和解法
题目#xff1a; 给你一个 只包含正整…题目链接416. 分割等和子集
文章讲解代码随想录 416. 分割等和子集讲解
视频讲解动态规划之背包问题这个包能装满吗| LeetCode416.分割等和子集
思路和解法
题目 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 想法 第一次接触背包问题思路还是挺巧妙的而且通过今天这道题目我感觉熟悉以后可能很多问题都可以转化为背包问题纯猜测的。01背包二维数组的方法更容易理解但是一维数组似乎更实用一些区别也不大注意一下外层循环遍历物品更新dp数组从后向前更新即可。
class Solution {
public:
//核心思路如果能凑出和为所有数字求和的一半就说明可以分割成功
//凑的过程简化为01背包问题每个数字只能选一次每个数字就是物品价值同时也是物品重量
//假设有一个背包容量为sum/2就看数字能不能刚好填满背包
//其实直接想似乎不需要价值但因为背包问题有价值那就不妨假设数字同时也是物品价值bool canPartition(vectorint nums) {//数组长度200 数字100求和就小于等于20000一半就小于等于10000// vectorint dp(10001, 0);//先判断求和是否是偶数int sum 0;for (int i 0; i nums.size(); i) {sum nums[i];}if (sum % 2 1) return false;int target sum / 2;vectorint 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;}
};
