dp专题7 分割等和子集
2024-01-02 16:49:33
本题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目:
思路:
由题意,题目意思是给出? 数组 nums? 找出两个子集它们的元素和相等。
这里两个自己的元素和相等,说明需要 数组 nums 总和可以平分,即 sum % 2 == 0
又因为子集不要求我们所取的元素是连续的,这里只有取或不取,所以我们试着取联想以下 01 背包
其中 容量是 我们的 sum / 2 ,只要我们取的 nums 元素之和 刚好满足 sum / 2 即可,所以我们的 元素中的? 价值 和?体积 都是 nums[] 元素值
代码详解如下:
class Solution {
public:
bool canPartition(vector<int>& nums) {
vector<int>dp(200*100+10,0); // 定义 dp 数组
int sum = 0; // 计算 (背包容量) 元素和
for(int &i:nums) sum += i;
if(sum % 2) return false; // 如果元素和无法平分,返回 false
else sum /= 2;
// 开始遍历元素
for(int &i:nums)
{
// 遍历(背包容量) 到达的平分元素和
for(int j = sum ;j >= i;--j)
{
dp[j] = max(dp[j],dp[j - i] + i);
}
}
return dp[sum] == sum;
}
};
最后提交:
文章来源:https://blog.csdn.net/hacker_51/article/details/135342603
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!