代碼隨想錄刷題第四十二天

今天是0-1背包問題，掌握了套路就不難了~~~

0-1背包問題理論基礎（二維數組篇）卡碼網第46題

題目思路：

代碼實現：

input_line = input()  # 讀取一行輸入
mn = input_line.split()
m, n = int(mn[0]), int(mn[1])
input_line = input().split()
weight = [int(input_str) for input_str in input_line]
input_line = input().split()
value = [int(input_str) for input_str in input_line]dp = [[0 for _ in range(n+1)] for _ in range(m)]if weight[0] <= n:for j in range(weight[0], n+1):dp[0][j] = value[0]for i in range(1, m):for j in range(1, n+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])print(dp[m-1][n])

0-1背包問題理論基礎（一維數組篇）卡碼網第46題

題目思路：

代碼實現：

input_line = input()  # 讀取一行輸入
mn = input_line.split()
m, n = int(mn[0]), int(mn[1])
input_line = input().split()
weight = [int(input_str) for input_str in input_line]
input_line = input().split()
value = [int(input_str) for input_str in input_line]dp = [0 for _ in range(n+1)]for i in range(m):for j in range(n, 0, -1):if j < weight[i]:dp[j] = dp[j]else:dp[j] = max(dp[j], dp[j-weight[i]]+value[i])print(dp[n])

分割等和子集 (LC 416)

題目思路：

代碼實現：

class Solution:def canPartition(self, nums: List[int]) -> bool:allsum = sum(nums)if allsum%2 == 1:return Falsetarget = allsum//2dp = [[0 for _ in range(target+1)] for _ in range(len(nums))]if nums[0]<=target:for j in range(nums[0], target+1):dp[0][j] = nums[0]for i in range(1, len(nums)):for j in range(1, target+1):if nums[i] > j:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])if dp[len(nums)-1][target] == target:return Trueelse:return False