当前位置：首页 > news >正文

代码随想录刷题第四十二天| 01背包问题，你该了解这些！ ● 01背包问题，你该了解这些！滚动数组 ● 416. 分割等和子集

news 2025/8/7 19:40:51

代码随想录刷题第四十二天

今天是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