网站建设投资风险分析,用户体验设计原则,好听的网站名称,建网站带支付链接题目#xff1a; 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
示例 1#xff1a; 输入#xff1a;nums [1,5,11,5] 输出#xff1a;true 解释#xff1a;数组可以分割成 [1, 5, 5] 和 …题目 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1 输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2 输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。 思路 1.dp数组以及下标的含义 dp[j] 表示 容量为j的背包所背的物品价值最大可以为dp[j]。 该题中每一个元素的数值既是重量也是价值。 那么如果背包容量为target dp[target]就是装满 背包之后的重量 所以 当 dp[target] target 的时候背包就装满了。 拿输入数组[1, 5, 11, 5]举例 dp[7] 只能等于 6因为 只能放进 1 和 5。 而dp[6] 就可以等于6了放进1 和 5那么dp[6] 6说明背包装满了。 2.递推公式 dp[j] max(dp[j], dp[j - weight[i]] value[i]); 3.dp数组如何初始化 dp[0]一定是0。 如果题目给的价值都是正整数那么非0下标都初始化为0就可以了如果题目给的价值有负数 那么非0下标就要初始化为负无穷。 4.遍历顺序 如果使用一维dp数组物品遍历的for循环放在外层遍历背包的for循环放在内层且内层for循环倒序遍历 5.推导dp数组 dp[j]的数值一定是小于等于j的。 如果dp[j] j 说明集合中的子集总和正好可以凑成总和j理解这一点很重要。 容量为j的背包所背的最大价值为dp[j] nums数组中既是重量也是价值 如果装满dp[target]这个背包最大价值就是target,那么target就装满了 class Solution {
public:bool track(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];}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]);}}//如果得到的容量为target的背包所背的最大价值刚好为target//说明可以实现if (dp[target] target)return true;return false;}
};int main() {vectorint nums { 1, 5, 11, 5 };Solution ss;cout ss.track(nums) endl;return 0;
}
