目录
0-1背包问题
应用
应用1：Leetcode.416
题目
分析
设 \(dp[i][j]\) 表示取前 \(i\) 个元素，可以凑成和为 \(j\) 的种类是否大于 \(0\)。同时假设，设数组 \(nums\) 的和为 \(S\) ，长度为 \(n\)。
如果 \(S\) 不能被 \(2\) 整除，那么，所有的元素肯定不能分割为等和子集。
如果 \(S\) 可以被 \(2\) 整除，那么，我们就可以将数组中的元素看出物品，背包容量为 \(S/2\)，题目就可以转换为0-1背包问题，最后答案就是 \(dp[i][S/2]\) 。
边界条件
边界条件就是凑成和为零的方案，即对于任何数字都不选，它也对应一种方法，所以
\[dp[i][0] = true, \quad 0 \le i \lt n \]状态转移
对于数组中的任意一个元素 \(nums[i]\) ，都有两种选择：
- 如果不选择当前元素，则当前状态与 \(dp[i-1][j]\) 相同；
- 如果选择当前元素，则当前状态与 \(dp[i - 1][j-nums[i]]\) 相同。
也就是说，我们只需要从上述两种方案中，选择一个结果为 \(true\) 的方案即可，所以，状态转移方程：
\[dp[i][j] = dp[i - 1][j] \ | \ dp[i - 1][j - nums[i - 1]], \quad nums[i - 1] \le j \le S/2 \]代码实现
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
_sum = sum(nums)
if _sum % 2 != 0:
return False
_sum = _sum // 2
dp = [[False for _ in range(_sum + 1)] for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True
for i in range(1, n + 1):
for j in range(1, _sum + 1):
# 背包容量不足，不能装入nums[i-1]
if j < nums[i-1]:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i - 1]]
return dp[n][_sum]
对其压缩状态，优化后的实现：
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
_sum = sum(nums)
if _sum % 2 != 0:
return False
_sum = _sum // 2
dp = [False] * (_sum + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(_sum, 0, -1):
if j >= nums[i - 1]:
dp[j] = dp[j] | dp[j - nums[i - 1]]
return dp[_sum]