济南网站推广优化_桂林 网_seo综合检测_网络销售怎么找客源

leetcode 416 分割等和子集

今日的主要内容是背包问题（0 - 1背包问题）

背包问题分为物品的重量和价值以及背包的最大承重，求得在背包最大承重范围内的最大价值

求取 dp[i][j] 有两种情况：

1. 放物品i
2. 还是不放物品i

初步递推公式：dp[ i ][ j ] = max(dp[ i - 1 ][ j ], dp[ i - 1][ j - weight[ i ]] + value[ i ])

滚动数组：dp[ j ] = max(dp[ j ],dp[ j - num ] + num)

class Solution:def canPartition(self, nums: List[int]) -> bool:total = sum(nums)target = total // 2if total % 2 != 0:return Falsedp = [0] * (target + 1)for i in range(len(nums)):for j in range(target, nums[i] - 1, -1):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])return dp[target] == target