【代码随想录训练营】【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 False
target = sum(nums) // 2
dp = [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 True
return 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]
