01背包问题—1(dp为二维数组):
文章链接
题目链接:卡码网 46
思路:
因为有物品和背包容量两个方面,因此我们使用二维数组保存递推的结果
- ① dp数组及下标的含义:
dp[i][j],其中 i 是第 i 个物品,j是背包容量,dp[i][j]表示在背包容量为 j 时,在[0, i]物品中任取所能取得的最大价值 - ② 递推公式:
根据是否取物品 i 来确定递推公式:
1)如果不取物品 i ,那么dp[i][j] = dp[i - 1][j]
2)如果取物品 i,那么背包容量剩余 j - weight[i],在[0, i - 1]物品中任取所能取得的最大价值为dp[i - 1][j - weight[i]]。因此dp[i][j] = dp[i - 1][j - weight[i]] + value[i]
因此dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
当背包容量 j 能放下物品 i 时 - ③ 初始化:
物品 i 的范围为[0, M - 1],背包容量 j 的范围为[0, N]
因此设定的dp为M×(N + 1)的数组
dp = [[0] * (N + 1) for _ in range(M)]
初始化第0列为全0,因为背包容量为0时放不了任何东西
由递推公式可知,还需要初始化第0行,那么就是,如果背包容量不能放下第0物品,dp为0;否则为value[0]
for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]
- ④ 遍历方式
由于dp递推式中dp[i][j]需要的信息都在其左上方,因此只要是先遍历完左上方的都可以。
比如先遍历物品再遍历容量,或者先遍历容量再遍历物品。其中先物品后容量是比较好理解的 - ⑤ 举例:
背包重量 4,物品的重量及价值
推导的dp数组
感悟:
dp数组及下标的含义,初始化以及遍历时记得下标的含义从而得到正确的范围
01背包问题–2(dp为一维数组):
文章链接
题目链接:卡码网 46
二维dp数组的01背包递推式为:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]),其中 i 为物品下标, j 为背包容量,dp[i][j]为从下标为[0, i]的物品里任意取,放进容量为 j 的背包,价值总和最大是多少。
那么如果将第 i - 1行的内容复制到第 i 行,那么递推公式为
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
那么实际上就可以按行状态压缩为一维数组dp(将原来二维的压缩为了原来的一行)
递推式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
- ① dp数组及下标的含义
dp[j]表示背包容量为 j 能放进的最大价值 - ② 递推式
递推式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])(如果背包能放进下标为 i 的物品) - ③ 初始化
dp[0] = 0,背包容量为0放不了物品, j ≠ 0 如何初始化呢。查看递推式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]),每次取最大值,如果题目给的价值都是正整数,那么dp[j]初始化为0 - ④ 遍历顺序
1)倒序遍历背包容量:原因,由递推式可知, dp[j] = max(dp[j], dp[j - weight[i]] + value[i]),如果顺序遍历的话,同一个物品会被多次放进背包。如(还是拿上一次举例的物品和背包容量);
或者也可以这么理解,一维dp数组是由二维dp数组压缩而来,二维的递推式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]),那么一维递推式中的dp[j - weight[i]] + value[i]对应dp[i - 1][j - weight[i]] + value[i],也就是一维数组中dp[x](x =j - weight[i])应当为上一行的值,如果顺序遍历的话,那么dp[x]就是这一行的值,所以要逆序遍历让dp[x]仍然为上一行的值
为什么二维dp数组遍历时不用倒序,因为dp[i][j]由上一层即dp[i - 1][j]计算而来,遍历本层dp[i][j]时不会覆盖上一层的数据,或者说本层dp[i][j]不会被覆盖
2)只能先遍历物品再遍历背包容量:
因为遍历背包容量为逆序遍历,所以如果先遍历物品再遍历背包容量的话,那么每次比较的就是空背包中放入一个物品后的价值比较。也就是背包中只能放一个物品了。
需要注意的是: 因为dp初始化为0,因此遍历物品从0开始;内层循环逆序遍历背包容量只到weight[i]即可。 - ⑤ 举例
背包容量为4,物品的重量及价值如下
那么递推的dp为
class Solution():def bagSolution(self):material, bagweight = [int(x) for x in input().split()]weight = [int(x) for x in input().split()]value = [int(x) for x in input().split()]dp = [0] * (bagweight + 1) # 初始化为全0# 先遍历物品,后遍历背包容量for i in range(material): # 因为初始化为全0,所以第一个物品也要遍历# 内层循环从bagweight空间逐渐减少到当前材料所占空间for j in range(bagweight, weight[i] - 1, -1): # 倒序dp[j] = max(dp[j], dp[j - weight[i]] + value[i])# 输出dp[bagweight],即在给定N 背包空间可以携带的研究材料的最大价值return dp[-1]solution = Solution()
print(solution.bagSolution())
感悟:
状态压缩二维数组为一维数组,该一维数组是原二维数组的某一行。因为计算dp需要用到其左上角的数据,如果遍历背包容量时顺序遍历,那么左上角数据就会被覆盖,因此需要逆序遍历,且只能先遍历物品,后遍历背包
LeetCode 416.分割等和子集:
文章链接
题目链接:416.分割等和子集
思路:
- 将问题修改为适合01背包的解法(dp是求最大值)
首先本题的目标为在集合中能否找到总和为sum / 2的子集
可以使用回溯,但是需要剪枝让其不超时。本题我们使用背包问题求解。
背包问题常见有:01背包、完全背包、多重背包以及分组背包
如果一个物品可以重复放入背包,那么是完全背包问题;只能放入一次是01背包问题。本题中集合中的元素只能放入一次,因此是01背包问题。
怎么确定能将01背包问题套入本题:
- 背包体积为 sum / 2
- 背包要放入的物品的重量为元素的数值,价值也为元素的数值
- 如果背包正好装满,说明找到了总和为sum / 2的子集
- 背包中每个元素都不能重复放入
动规五部曲 - ① dp及下标的含义
01背包中,dp[j]:表示容量为 j 的背包,所装的物品最大价值为dp[j]
应用到本题中: dp[j]表示背包总容量为 j ,放入物品后,背的最大价值,即最大重量为dp[j]
那么当dp[target] == target时,背包就正好装满了 - ② 递推公式
01背包递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
本题中物品的重量和价值都是nums[i]
因此递推公式为dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) - ③ 初始化
从dp[j]的定义来说,dp[0]初始化为0,因为题目给的的价值都是正整数,因此非0下标都初始化为0。如果题目给的价值有负数,那么非0下标要初始化为负无穷 - ④ 遍历顺序
先物品后背包容量,且背包容量逆序遍历 - ⑤ 举例
dp[j] <= j(一定成立)
如果dp[j] == j,那么集合可以被分为子集和相同的两个子集
输入[1, 5, 11, 5]
class Solution:def canPartition(self, nums: List[int]) -> bool:if len(nums) == 1:return False_sum = sum(nums)if _sum % 2 == 1: # 集合和为奇数return Falsetarget = _sum // 2dp = [0] * (target + 1)# 先物品后背包重量for num in nums:# 背包重量逆序遍历for j in range(target, num - 1, -1):dp[j] = max(dp[j], dp[j - num] + num)return dp[-1] == target
- 01背包更进一步修改贴合本题(dp值为True or False)
因为题目要求的是能否将数组分为和相等的两个集合,那么实际上dp数组的值可以为True or False。
动规五部曲
- ① dp及下标的含义
dp[j] : 表示背包容量为 j 能否从集合中找到元素刚好填满背包,能否为dp[j] - ② 递推
考虑是否要将物品 i(即元素 i)加入背包中
1)如果不加入:dp[j] = dp[j]
2)如果加入:dp[j] = d[j - nums[i]]
因此dp[j] = dp[j] or dp[j - nums[i]](因为只要有一个成立就可以了) - ③ 初始化
dp[0] = True(背包为空,相当于可以从集合中找到元素刚好填满背包,即一个都不放),由递推公式dp[j] = dp[j] or dp[j - nums[i]]得,下标非0应当初始化为False(False or x = x,这样让dp数组在遍历时求两个的or,而不是被初始值覆盖) - ④ 遍历顺序
即一维01背包遍历顺序。先物品后背包,背包容量逆序遍历 - ⑤ 举例
"""
思路里面的一维dp数组
使用的是0和1,代表False和True
"""
class Solution:def canPartition(self, nums: List[int]) -> bool:if len(nums) == 1: # 只有一个元素return FalsesumNums = sum(nums)if sumNums % 2 == 1: # 集合总和为奇数return False# 动态规划,是否能从集合中挑选出元素满足和为sumNums // 2dp = [0] * (sumNums // 2 + 1)dp[0] = 1 # 初始化# 先遍历集合中的元素for i in range(len(nums)):for j in range(sumNums // 2, nums[i] - 1, -1):dp[j] = (dp[j] or dp[j - nums[i]])if dp[-1] == 1:return Trueelse:return False"""
使用二维dp数组
需要注意的是dp数组的行数为len(nums) + 1,第0行没有物品,为空集。
- dp[i][j]为在集合[1, i]能否找到元素正好填满容量为j的背包,dp[i][j]为能否
- 递推公式为dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
- 初始化:第0列初始化为True(背包为空),那么第0行如何初始化呢
- 如果第0行是物品1能否正好填满容量为j的背包,那么应当dp[0][nums[0]] = True,那么需要考虑到 nums[i] > j的情况。所以不如直接让第0行没有物品,为空集,初始化为False
- 因为第0行没有物品,因此物品从第1行开始,那么nums[i]对应第 i + 1行
"""
class Solution:def canPartition(self, nums: List[int]) -> bool:if len(nums) == 1:return False_sum = sum(nums)if _sum % 2 == 1:return Falsetarget = _sum // 2dp = [[False] * (target + 1) for _ in range(len(nums) + 1)]# 初始化# 第0列应当为True(j = 0),第0行是没有物品,即空集的情况for i in range(len(nums) + 1):dp[i][0] = True# 遍历递推for i in range(1, len(nums) + 1):for j in range(1, target + 1):if j >= nums[i - 1]: # nums[i - 1]对应第 i 行dp[i][j] = (dp[i - 1][j] or dp[i - 1][j - nums[i - 1]])else:dp[i][j] = dp[i - 1][j]return dp[-1][-1]
感悟:
01背包思路用在其应用题上,需要明确dp、物品重量和价值分别是什么,以及动态规划五部曲
学习收获:
01背包问题的二维dp数组、一维dp数组以及01背包问题的应用