网站布局模式,网络营销八大工具,什么是电商平台怎么加入电商平台,植物网站设计方案背包问题#xff0c;416. 分割等和子集 背包问题416. 分割等和子集 背包问题
有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。
卡玛网的… 背包问题416. 分割等和子集 背包问题416. 分割等和子集 背包问题
有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
卡玛网的代码参考
n, bagweight map(int, input().split())weight list(map(int, input().split()))
value list(map(int, input().split()))dp [[0] * (bagweight 1) for _ in range(n)]for j in range(weight[0], bagweight 1):dp[0][j] value[0]for i in range(1, n):for j in range(bagweight 1):if j weight[i]:dp[i][j] dp[i - 1][j]else:dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i])print(dp[n - 1][bagweight])
一维dp 的01背包初始化和遍历顺序更简单一维dp数组的背包在遍历顺序上和二维不同使用一维dp数组物品遍历的for循环放在外层遍历背包的for循环放在内层且内层for循环倒序遍历。
n, bagweight map(int, input().split())
weight list(map(int, input().split()))
value list(map(int, input().split()))dp [0] * (bagweight 1) # 创建一个动态规划数组dp初始值为0dp[0] 0 # 初始化dp[0] 0,背包容量为0价值最大为0for i in range(n): # 应该先遍历物品如果遍历背包容量放在上一层那么每个dp[j]就只会放入一个物品for j in range(bagweight, weight[i]-1, -1): # 倒序遍历背包容量是为了保证物品i只被放入一次dp[j] max(dp[j], dp[j - weight[i]] value[i])print(dp[bagweight])
416. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.
参考代码重点掌握一维的方法。
class Solution:def canPartition(self, nums: List[int]) - bool:_sum 0# dp[i]中的i表示背包内总和# 题目中说每个数组中的元素不会超过 100数组的大小不会超过 200# 总和不会大于20000背包最大只需要其中一半所以10001大小就可以了dp [0] * 10001for num in nums:_sum num# 也可以使用内置函数一步求和# _sum sum(nums)if _sum % 2 1:return Falsetarget _sum // 2# 开始 0-1背包for num in nums:for j in range(target, num - 1, -1): # 每一个元素一定是不可重复放入所以从大到小遍历dp[j] max(dp[j], dp[j - num] num)# 集合中的元素正好可以凑成总和targetif dp[target] target:return Truereturn False简化
class Solution:def canPartition(self, nums: List[int]) - bool:if sum(nums) % 2 ! 0:return Falsetarget sum(nums) // 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二维DP
class Solution:def canPartition(self, nums: List[int]) - bool:total_sum sum(nums)if total_sum % 2 ! 0:return Falsetarget_sum total_sum // 2dp [[False] * (target_sum 1) for _ in range(len(nums) 1)]# 初始化第一行空子集可以得到和为0for i in range(len(nums) 1):dp[i][0] Truefor i in range(1, len(nums) 1):for j in range(1, target_sum 1):if j nums[i - 1]:# 当前数字大于目标和时无法使用该数字dp[i][j] dp[i - 1][j]else:# 当前数字小于等于目标和时可以选择使用或不使用该数字dp[i][j] dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]return dp[len(nums)][target_sum]一维DP
class Solution:def canPartition(self, nums: List[int]) - bool:total_sum sum(nums)if total_sum % 2 ! 0:return Falsetarget_sum total_sum // 2dp [False] * (target_sum 1)dp[0] Truefor num in nums:# 从target_sum逆序迭代到num步长为-1for i in range(target_sum, num - 1, -1):dp[i] dp[i] or dp[i - num]return dp[target_sum]
