背包問題介紹
-
- 背包：最大容量（體積妒蛇，重量）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數(shù)組.
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數(shù)組: 先遍歷物品, 再遍歷背包.
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數(shù)組: 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)
- 空間優(yōu)化
- dp[i][j]由dp[i-1][j]和dp[i-1][j-weight[i]]得到.物品空間維數(shù)可壓縮 (滾動數(shù)組)。
- 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_為偶數(shù)）
- 物品：數(shù)字
- 重量=nums[i]
- 價值=nums[i]
- 0-1背包（每個數(shù)字使用一次）
- dp[i][j]: 數(shù)字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
- 空間優(yōu)化（內(nèi)層背包逆序遍歷）
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
