[代码随想录]Day36-动态规划part04
题目：
思路：
只有确定了如下四点，才能把01背包问题套到本题上来。
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
代码：
func canPartition(nums []int) bool {
sum := 0
for _, x := range nums {
sum += x
}
if sum % 2 != 0 { // 如果不是偶数，必然不可能两个子集相等
return false
}
sum /= 2
dp := make([]int, sum + 1)
for i:=0;i<len(nums);i++ {
for j:=sum;j>=nums[i];j-- {
dp[j] = max(dp[j],dp[j-nums[i]] + nums[i])
}
}
if dp[sum] == sum { // 可以让子集等于一半的全集
return true
}
return false
}
func max(a,b int)int {
if a > b {
return a
}
return b
}
参考：
代码随想录