【Leetcode】背包问题-416. 分割等和子集
【Leetcode】背包问题-416. 分割等和子集
题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
思路
- 如果可以分割等和子集 那么背包中正好装下一半的数值 sum / 2
- 背包要放进的物品是元素的数值,价值也是元素的数值
- 每一个元素只能放入一次
- 确定dp数组 的含义
- dp[j]表示容量为j的背包最大容量的物品价值
- 确定一维dp数组推导公式
- dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
- 题目给出的元素都是正整数 所以dp数组全部初始化为0 如果有负数 全部初始化为负无穷
- 保证dp数组在递归公式中取得是最大值 而不是被初始值覆盖
代码
class Solution {
public:
bool canPartition(vector<int>& nums) {
// 如果可以分割等和子集 那么背包中正好装下一半的数值 sum / 2
// 背包要放进的物品是元素的数值,价值也是元素的数值
// 每一个元素只能放入一次
// 计算目标数值 target = sum / 2
int sum = 0;
for(int i = 0; i < nums.size(); i++)
{
sum += nums[i];
}
if(sum % 2 == 1)
{
return false;
}
int target = sum / 2;
// 确定dp数组 的含义
// dp[j]表示容量为j的背包最大容量的物品价值
vector<int> dp(10001,0);
// 确定一维dp数组推导公式
// dp[j] = max(dp[j],dp[j - nums[i]] + nums[i]);
// 题目给出的元素都是正整数 所以dp数组全部初始化为0 如果有负数 全部初始化为负无穷
// 保证dp数组在递归公式中取得是最大值 而不是被初始值覆盖
// 先遍历Nums数组 在遍历背包 这里的bagWeight = sum / 2
// 记住模板
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;
}
};