做网站推广有用吗,wordpress网站显示不全,泰州网站建设物美价廉,天元建设集团有限公司大同【代码随想录训练营】【Day 44】【动态规划-4】| 卡码 46#xff0c; Leetcode 416
需强化知识点
背包理论知识
题目
卡码 46. 携带研究材料
01 背包理论基础01 背包理论基础#xff08;滚动数组#xff09;01 背包 二维版本#xff1a;dp[i][j] 表示从下标为[0-i]的物…【代码随想录训练营】【Day 44】【动态规划-4】| 卡码 46 Leetcode 416
需强化知识点
背包理论知识
题目
卡码 46. 携带研究材料
01 背包理论基础01 背包理论基础滚动数组01 背包 二维版本dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少注意 遍历和初始化时 n 要取到01 背包 一维版本dp[j]为 容量为j的背包所背的最大价值注意 先遍历 物品再重量倒序遍历 def func(m, n, weight, value):# dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。# 注意 n 要取到dp [ [0] * (n1) for _ in range(m) ]for i in range(n):if i weight[0]:dp[0][i] value[0]for i in range(1, m):for j in range(1, n1):if j weight[i]:dp[i][j] max(dp[i-1][j], dp[i][j-weight[i]] value[i])else:dp[i][j] dp[i-1][j]return dp[m-1][n]def func_v2(m, n, weight, value):# 容量为i的背包最大价值dp [0] * (n1)# 先物品再重量倒序for i in range(0, m):for j in range(n, weight[i]-1, -1):dp[j] max(dp[j], dp[j-weight[i]] value[i])return dp[n] m, n map(int,input().split())
weight list(map(int,input().split()))
value list(map(int,input().split()))print(func_v2(m, n, weight, value))416. 分割等和子集
动态规划01背包问题重量为 target价值为数值使用 回溯剪枝的方法会超时注意对于返回 布尔值的处理
class Solution:def canPartition(self, nums: List[int]) - bool:if sum(nums) % 2:return Falsetarget sum(nums) // 2dp [0] * (target1)for i in range(len(nums)):for j in range(target, nums[i]-1, -1):dp[j] max(dp[j], dp[j - nums[i]] nums[i])if dp[j] target:return Truereturn False# 回溯 剪枝 超时注意bool 类型返回值的方式目前只能想到这种# def backtracking(path, result, startIndex, target, nums):# if startIndex len(nums) or sum(path) target:# return# if sum(path) target:# result[0] True# return# for i in range(startIndex, len(nums)):# if sum(path) nums[i] target:# break# path.append(nums[i])# backtracking(path, result, i1, target, nums)# path.pop()# result [False]# if sum(nums) % 2:# return False# else:# nums.sort()# backtracking([], result, 0, sum(nums) // 2, nums)# return result[0]
