代碼隨想錄算法訓練營Day 42| 動態規劃part04 | 01背包問題理論基礎I、01背包問題理論基礎II、416. 分割等和子集

---

---

01背包問題理論基礎

一、01背包問題

有n件物品和一個最多能背重量為w 的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大。

二、一維dp

def test_1_wei_bag_problem(weight, value, bagWeight):# 初始化dp = [0] * (bagWeight + 1)for i in range(len(weight)):  # 遍歷物品for j in range(bagWeight, weight[i] - 1, -1):  # 遍歷背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])return dp[bagWeight]if __name__ == "__main__":weight = [1, 3, 4]value = [15, 20, 30]bagweight = 4result = test_1_wei_bag_problem(weight, value, bagweight)print(result)

三、二維dp

def test_2_wei_bag_problem1(weight, value, bagweight):# 二維數組dp = [[0] * (bagweight + 1) for _ in range(len(weight))]# 初始化for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]# weight數組的大小就是物品個數for i in range(1, len(weight)):  # 遍歷物品for j in range(bagweight + 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(weight) - 1][bagweight]if __name__ == "__main__":weight = [1, 3, 4]value = [15, 20, 30]bagweight = 4result = test_2_wei_bag_problem1(weight, value, bagweight)print(result)

---

416. 分割等和子集

題目鏈接

一、dp

class Solution(object):def canPartition(self, nums):""":type nums: List[int]:rtype: bool"""if sum(nums) % 2 != 0:return False# dp[i]中的i表示背包內總和# 題目中說：每個數組中的元素不會超過 100，數組的大小不會超過 200# 總和不會大于20000，背包最大只需要其中一半，所以10001大小就可以了2dp = [0]*10001 # 或者dp =[0]*(target+1)target = sum(nums)//2for i in range(1,len(nums)):for j in range(target,nums[i]-1,-1):dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])      return dp[target]==target