网站开发平台 eclipse,谁帮助汉字叔叔做网站,梅州建站推荐,wordpress 图标代码随想录刷题第四十二天
今天是0-1背包问题#xff0c;掌握了套路就不难了~~~
0-1背包问题理论基础#xff08;二维数组篇#xff09;卡码网第46题
题目思路#xff1a; 代码实现#xff1a;
input_line input() # 读取一行输入
mn input_line.split()
m, n int…代码随想录刷题第四十二天
今天是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(n1)] for _ in range(m)]if weight[0] n:for j in range(weight[0], n1):dp[0][j] value[0]for i in range(1, m):for j in range(1, n1):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(n1)]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(target1)] for _ in range(len(nums))]if nums[0]target:for j in range(nums[0], target1):dp[0][j] nums[0]for i in range(1, len(nums)):for j in range(1, target1):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
