[背包基础]
题目:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
1、二维方式解决背包问题
class Solution:
def solve_bag(self, weight, value, bag_weight):
# dp[i][j] 代表物品为 i,背包重量为 j 的最大价值
dp = [[0]*(bag_weight+1) for _ in range(len(value))]
# 初始化数组
for j in range(weight[0], bag_weight + 1):
dp[0][j] = value[0]
# 遍历
for i in range(1, len(value)): # 先遍历物品
for j in range(bag_weight + 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])
return dp[len(value) - 1][bag_weight]
2、一维方式解决背包问题
注意点:倒序遍历，保证物品 i 只被放入一次
dp[j] 代表背包容量为 j 的背包的价值总量为 dp[j]。
class Solution:
def solve_bag(self, weight, value, bag_weight):
# dp[j] 代表背包重量为 j 的最大价值
dp = [0] * (bag_weight + 1)
# 初始化数组
dp[0] = 0
# 遍历
for i in range(len(value)): # 先遍历物品
for j in range(bag_weight, weight[i] - 1, -1): # 遍历背包容量
# 递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
return dp[bag_weight]
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2 != 0:
return False
target = sum(nums) // 2
dp = [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[target] == target