【代码随想录训练营】【Day 44】【动态规划-4】| 卡码 46， Leetcode 416

【代码随想录训练营】【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] * (n+1) 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, n+1):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] * (n+1)# 先物品，再重量（倒序）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] * (target+1)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, i+1, 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]