中国旅游网站排名,菏泽微信小程序制作,华为建站,苏州官网网站首页目录 题目描述#xff1a;示例 1#xff1a;示例 2#xff1a;代码实现#xff1a; 题目描述#xff1a;
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
示例 1#xff1a;
输入#… 目录 题目描述示例 1示例 2代码实现 题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5] 输出true 解释数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2
输入nums [1,2,3,5] 输出false 解释数组不能分割成两个元素和相等的子集。
代码实现
class Solution {public boolean canPartition(int[] nums) {if (nums.length 1) {// 元素个数为1直接为假return false;}int sum 0;// 数组所有元素之和int max 0;// 数组内最大元素for (int i 0; i nums.length; i) {sum nums[i];if (max nums[i]) {max nums[i];}}if (sum % 2 ! 0) {// 如果元素之和为奇数则必然不可能拆分为等和字迹return false;}int target sum / 2;// 任一子集内元素之和if (max target) {return false;// 如果最大值超过元素之和的一半则必然不能等和}// 转化为01背包问题nums[i]既是物品价值也是物品重量int[] dp new int[target 1];// dp[j]表示容量为j的背包的最大价值// 由于本题物品单价为1价值重量所有尽可能装满背包即可// 采用一维数组压缩状态滚动数组的方式for (int i 0; i nums.length; i) {// 先遍历物品for (int j target; j nums[i]; j--) {// 再倒序遍历背包背包容量j要大于物品大小nums[i]dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);// 状态转移方程:两种情况的较大值// 1.背包不放物品nums[i]依然是上一轮背包状态dp[j]// 2.放物品nums[i](背包j-当前物品重量nums[i])时的dp最大价值 当前放入物品价值nums[i]}}return dp[target] target;// 题意求数组中是否存在一组和为target的元素集合// 转化成01背包问题是否存在若干物品能够装入容量为target的背包}
}
