背包问题介绍
-
- 背包：最大容量（体积，重量）j
- 物品：
- 体积，重量 weight[i]
- 价值 value[i]
- 以下介绍0-1背包：每个物品最多只能使用一次。
- dp[i][j]: 物品0,1,...,i中取若干个; 背包容量为j；最大价值
- 递推公式：
- 第i个物品：不取 vs 取 (注意要先判断是否可取)
- dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]), j >= weight[i]
- dp[i][0] = 0
dp[0][j] = 0, j < weight[0]
dp[0][j] = value[0], j >= weight[0] - 遍历顺序
- 先物品，再背包 (组合，带去重功能)
- 先背包，再物品 （排列）
def test_2_wei_bag_problem1(bag_size, weight, value) -> int:
rows, cols = len(weight), bag_size + 1
dp = [[0 for _ in range(cols)] for _ in range(rows)]
# 初始化dp数组.
for i in range(rows):
dp[i][0] = 0
first_item_weight, first_item_value = weight[0], value[0]
for j in range(1, cols):
if first_item_weight <= j:
dp[0][j] = first_item_value
# 更新dp数组: 先遍历物品, 再遍历背包.
for i in range(1, len(weight)):
cur_weight, cur_val = weight[i], value[i]
for j in range(1, cols):
if cur_weight > j: # 说明背包装不下当前物品.
dp[i][j] = dp[i - 1][j] # 所以不装当前物品.
else:
# 定义dp数组: dp[i][j] 前i个物品里，放进容量为j的背包，价值总和最大是多少。
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight] + cur_val)
print(dp)
if __name__ == "__main__":
bag_size = 4
weight = [1, 3, 4]
value = [15, 20, 30]
test_2_wei_bag_problem1(bag_size, weight, value)
- 空间优化
- dp[i][j]由dp[i-1][j]和dp[i-1][j-weight[i]]得到.物品空间维数可压缩 (滚动数组)。
- dp[j]: 容量为j的背包（当前）所背物品的最大价值
- 每个物品只能用一次，遍历j需要倒序
def test_1_wei_bag_problem():
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
# 初始化: 全为0
dp = [0] * (bag_weight + 1)
# 先遍历物品, 再遍历背包容量
for i in range(len(weight)):
for j in range(bag_weight, weight[i] - 1, -1):
# 递归公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp)
test_1_wei_bag_problem()
416. 分割等和子集
- 思路
- example
- 背包：容量target = sum_ //2 (sum_为偶数）
- 物品：数字
- 重量=nums[i]
- 价值=nums[i]
- 0-1背包（每个数字使用一次）
- dp[i][j]: 数字nums[0],...,nums[i]中选取若干个，背包容量为target所能容纳的最大价值（子集和）。
- 目标：return dp[n-1][target] == target
- 递推公式：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[j])
- 复杂度. 时间：
, 空间:
,
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
sum_ = sum(nums)
if sum_ % 2 != 0:
return False
target = sum_ // 2
dp = [[0 for _ in range(target+1)] for _ in range(n)]
for j in range(nums[0], target+1):
dp[0][j] = nums[0]
for i in range(1, n):
for j in range(1, target+1):
if j < nums[i]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i])
return dp[n-1][target] == target
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
sum_ = sum(nums)
if sum_ % 2 != 0:
return False
target = sum_ // 2
dp = [[0 for _ in range(target+1)] for _ in range(n)]
for j in range(target+1):
if j >= nums[0]:
dp[0][j] = nums[0]
for i in range(n):
for j in range(target+1):
if j < nums[i]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
return dp[n-1][target] == target
- 空间优化（内层背包逆序遍历）
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
sum_ = sum(nums)
if sum_ % 2 != 0:
return False
target = sum_ // 2
dp = [0 for _ in range(target+1)]
for j in range(nums[0], target+1):
dp[j] = nums[0]
for i in range(1, n):
for j in range(target, 0, -1):
if j >= nums[i]:
dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
return dp[target] == target
- 可只记录dp[i][j]的True/False值（可行性）, 下面给出二维DP版本
- 注意dp[i][j]关于背包容量j这里是“=”逻辑， 不是最多逻辑。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
sum_ =sum(nums)
if sum_ % 2 != 0:
return False
target = sum_ // 2
dp = [[False for _ in range(target+1)] for _ in range(n)]
for j in range(target+1):
if j == nums[0]:
dp[0][j] = True
break
for i in range(1, n):
for j in range(target+1):
if j < nums[i]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
return dp[n-1][target]
- dfs, 记亿化dfs
TBA
