## 为什么是 0-1 背包 ```bash 1. 转化过程 原问题：给每个数前面加 + 或 -，使表达式结果等于 target 设所有带 + 号的数之和为 x，所有带 - 号的数之和为 y 则 x + y = total，x - y = target 解得 x = (total + target) / 2 问题转化为： 从 nums 中选若干个数，使它们的和等于 x → 每个数只能选一次（选或不选） → 这就是 0-1 背包 2. 与标准 0-1 背包的对应关系 物品：nums 中的每个数 物品重量：num（数值本身） 物品价值：num（本题价值等于重量） 背包容量：x = (total + target) / 2 物品数量：每个物品最多选 1 次 3. 特殊之处 本题求的是方案数，不是最大价值。 但背包类型仍然是 0-1 背包，只是 dp 含义变了： 标准 0-1 背包：dp[j] = 容量为 j 时的最大价值 本题： dp[j] = 凑出和为 j 的方案数 4. 遍历顺序仍然是 0-1 背包的方式 for num in nums: # 先遍历物品 for j in range(x, num-1, -1): # 容量倒序（保证每个数只用一次） dp[j] += dp[j - num] ``` **0-1 背包的三种常见问法** | 问法 | dp 含义 | 转移方程 | 例题 | |:---|:---|:---|:---| | 最大价值 | dp[j] = 最大价值 | max(dp[j], dp[j-w]+v) | 标准 0-1 背包 | | 方案数 | dp[j] = 方案数 | dp[j] += dp[j-w] | 494 目标和 | | 可行性(是否存在) | dp[j] = True/False | dp[j] = dp[j] or dp[j-w] | 416 分割等和子集 | 三种问法的背包类型都是 0-1 背包，只是 dp 数组存的东西不同。 ## 题解代码 ```python class Solution: # 给你一个非负整数数组 nums 和一个整数 target 。 # 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： # 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 # 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 def findTargetSumWays(self, nums: List[int], target: int) -> int: # 设 添加+号的所有数的和为x 添加-号的所有数的和为y 所有数之和为total # 则 x - y = target -> x - ( total - x ) = target -> x = ( total + target ) / 2 # 所以问题转化为:从nums中选择若干个数,使得选择的树之和为 x # 进一步转化:从nums中选择若干个数,使得容量为x的价值最大,最大价值是x。 """ 总结: 对于分组问题,若物品的体积(质量)、价值是同一个维度的值,果断转化成背包问题。 """ # 本题要求的是nums内元素之前添加符号,求满足条件的表达式种类, 是组合问题。 total = 0 for v in nums: total += v if abs( target ) > total: return 0 if ( total + target ) % 2 == 1: return 0 # 一定无法使得最大价值为x # 能够转换成背包问题后 dp的含义按照要求定义 # 这里 dp[ i ] 表示 容积为i的背包 最大价值为i 的表达式种类 n = len( nums ) x = ( total + target ) // 2 dp = [ 0 for _ in range( x + 1 ) ] dp[ 0 ] = 1 for i in range( n ): for j in range( x, nums[ i ] - 1, -1 ): dp[ j ] = dp[ j ] + dp[ j - nums[ i ] ] return dp[ -1 ] ```