赞
踩
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5]
输出:false
解释:数组不能分割成两个元素和相等的子集。
思路:
思路:这里说为什么可以划分为问题:
1)0-1背包问题是说往背包放入商品使得背包内物品价值最大,而这里是找到数组使数组的和等于总集合和的一半。
2)同样是从给定列表里面取元素取的元素等于一个值,一个是最大值一个是给定值,所以后者相当于把背包容量定义为了集合总和的一半,那么当放入的元素和等于背包容量也就是说找到了一个子集,那么剩下的子集和也必定是背包容量的一半。
注意物品的价值在这里就是物品本身而已,最后只要判断dp右下角元素的值是否和背包容量是不是相同即可。
class Solution: def canPartition(self, nums: List[int]) -> bool: sums = int((sum(nums))/2) #集合和为奇数时显然是不可以的 if sum(nums) % 2 != 0: return False else: # 创建背包 dp = [[0 for j in range(sums+1)] for i in range(len(nums))] #初始化背包 for i in range(len(nums)): dp[i][0] = 0 for j in range(nums[0],sums+1): dp[0][j] = nums[0] for i in range(1,len(nums)): for j in range(sums+1): if j < nums[i]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]) return dp[len(nums) - 1][sums] == sums
这里仅供自己复习使用,也欢迎批评指正。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。