动态规划 - 背包问题 - 01背包

 01背包问题

二维数组

1. 确定dp数组（dp table）以及下标的含义：dp[i][j]-下标为[0,i]的物品，任取放容量为j的背包中的最大价值
2. 确定递推公式：dp[i][j] = max(dp[i-1][j]（不放物品i), dp[i-1][j-weight[i]]+value[i]（放物品i）)
3. dp数组如何初始化: dp[i][0]=0,dp[0][j]很复杂
4. 确定遍历顺序：二维数组实现的01背包，物品和背包遍历先后顺序无所谓

一维数组--滚动数组--覆盖,把上一层数组拷贝下来

1. 确定dp数组（dp table）以及下标的含义：dp[j]-容量为j的背包所背的最大价值
2. 确定递推公式：dp[j]= max(dp[j], dp[j-weight[i]]+value[i])
3. dp数组如何初始化：dp[0] = 0
4. 确定遍历顺序：先物品再背包，背包需要倒序

常见变形

• 至多装xx容量，求方案数/最大价值和
• 恰好装xx容量，求方案数/最大/最小价值和
• 至少装xx容量，求方案数/最小价值和

@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
def dfs(i: int, c: int) -> int:if i < 0:return 0if c < w[i]:return dfs(i - 1, c)  # 只能不选return max(dfs(i - 1, c), dfs(i - 1, c - x)  # 不选 + 选
return dfs(len(nums) - 1, m)

1:1 翻译成递推

        n = len(nums)f = [[0] * (m + 1) for _ in range(n + 1)] #m:背包容量f[0][0] = 1for i, x in enumerate(nums):for c in range(m + 1):if c < x:f[i + 1][c] = f[i][c]  # 只能不选else:f[i + 1][c] = f[i][c] + f[i][c - x]  # 不选 + 选return f[n][m]

优化成一维

n = len(nums)
dp = [0]*(target+1)
dp[0] = 1
for i, x in enumerate(nums):for c in range(target+1, x-1, -1):dp[c] = max(dp[c], dp[c - x])  
return dp[target]

416. 分割等和子集: 能否装满  max() target == dp[target]

中等

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

看是否可以分成两个子集，和都为总和/2，每个元素的值即是重量又是价值

抽象成背包问题：看容量为总和/2的背包是否能装满， 每个元素只能使用一次：0-1背包

解题步骤：
1. 确定dp数组（dp table）以及下标的含义：是否可以通过选择一些元素来构成和为 j 的子集，容量为j的背包能背的最大价值是否为j。dp[target]== target, dp[sum/2] == sum/2
2. 确定递推公式：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

                             dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
3. dp数组如何初始化：dp[0]=0, 
4. 确定遍历顺序：先物品再背包，背包需要倒序

代码随想录：时间只打败20% 

class Solution:def canPartition(self, nums: List[int]) -> bool:n = len(nums)s = sum(nums)if s%2 == 1: return False #总和除2有余数，不可能分成两个和一样的子集target = s //2dp=[0]*(target+1) #覆盖从 0 到 target 的所有可能和for i,x in enumerate(nums):#物品 nums[i] = xfor j in range(target,x-1,-1):
# 从后向前遍历（target到nums[i]），确保每个物品只被使用一次dp [j] = max(dp[j],dp[j-x]+x)return target == dp[target]

考虑 nums[i] 选或不选：

选：问题变成能否从 nums[0] 到 nums[i−1] 中选出一个和恰好等于 j−nums[i] 的子序列，即 dfs(i−1,j−nums[i])。

不选：问题变成能否从 nums[0] 到 nums[i−1] 中选出一个和恰好等于 j 的子序列，即 dfs(i−1,j)。

 f[i + 1][j] = j >= x and f[i][j - x] or f[i][j]

class Solution:def canPartition(self, nums: List[int]) -> bool:total = sum(nums)if total % 2 == 1: return False #和为奇数，不可能分成两个和一样的target = total // 2dp = [True]+[False] * target #dp[0]=truefor i,x in enumerate(nums): #枚举物品for j in range(target, x - 1, -1): #背包dp[j] = dp[j] or dp[j - x] return dp[target]

1049. 最后一块石头的重量 II：能装的最大价值： max ()

中等

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

把石头分为两堆，使两堆的重量最接近，即尽量找到sum//2的一堆。那么问题就转化为了在石头堆中找到重量和为sum//2的一部分元素。

石头的重量即价值

1. 确定dp数组（dp table）以及下标的含义：dp[j] -装满容量为j的背包的最大重量dp[j]
2. 确定递推公式: dp[j] = max(dp[j], dp[j-stone[i]]+stone[i])
3. dp数组如何初始化：dp[0] = 0 
4. 确定遍历顺序: 物品正序，背包倒序

注意返回值

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:s = sum(stones)target = s//2dp = [0]*(target+1)for i,x in enumerate(stones): #stone[i] =xfor j in range(target, x-1, -1):dp[j] = max (dp[j],dp[j-x]+x)return  s - 2*dp[target]#target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。#那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

494. 目标和：有多少种方式能装满：dp[j] = dp[j]+dp[j-x]

中等

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

正数p，负数部分的绝对值：s-p，则题目转化成s-（s-p）=target的方案数，p =(target+s)/2。装满容量为(target+s)/2的背包有多少种方法

注意点：s+target必须是偶数，nums[i]不为负--s(不为负)+target 需不为负

1. 确定dp数组（dp table）以及下标的含义：装满容量为j的背包有dp[j]种方法
2. 确定递推公式: dp[j] = dp[j]+dp[j-x]
3. dp数组如何初始化: dp[0]=1
4. 确定遍历顺序：0-1背包的遍历顺序

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:s = sum(nums)p = s+targetif p<0 or p%2: #s+target必须是偶数，nums[i]为正--s+target需不为负return 0p //=2dp = [0]*(p+1)dp[0] = 1for i,x in enumerate(nums):for j in range(p,x-1,-1):dp[j] = dp[j]+dp[j-x]return dp[p]

474. 一和零：背包最多物品个数

中等

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

 还是0-1背包问题：m n 可以理解为背包的两个维度（有两个重量约束，完全背包是一个物品可以放多次），求至多装的物品个数

"10"、"0001"、"111001"都是物品，只可以被放一次，所以还是0-1背包。

1. 确定dp数组（dp table）以及下标的含义：最多装i个0和j个1的背包的最大物品个数
2. 确定递推公式: dp[i][j] = max(dp[i-x][j-y]+1,dp[i][j])(物品有x个0，y个1，放和不放)
3. dp数组如何初始化: dp[0][0]=0
4. 确定遍历顺序：0-1背包的遍历顺序。物品正序，背包倒序

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0 for _ in range((n+1))]for _ in range(m+1)]# 物品for s in strs:cnt_0 = s.count("0") # 统计字符串中0的个数cnt_1 = s.count("1") # 统计字符串中1的个数# 背包for i in range(m, cnt_0-1, -1):for j in range(n, cnt_1-1,-1):dp[i][j] = max(dp[i-cnt_0][j-cnt_1]+1, dp[i][j])return dp[m][n]