代码随想录第36天

def hanshu():wupin, bagweight = [int(x) for x in input().split()]weight = [int(x) for x in input().split()]value = [int(x) for x in input().split()]dp = [[0]*(bagweight+1) for i in range(wupin)]  #dp[i][j]代表从物品【0,i-1】让任意取，背包重量j，达到的最大价值#初始化for j in range(weight[0],bagweight+1):dp[0][j] = value[0]for i in range(1, wupin):for j in range(1, bagweight+1):if j>=weight[i]:dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])else:dp[i][j] = dp[i-1][j]return dp[wupin-1][bagweight]maxs = hanshu()
print(maxs)

class Solution:def bag(self, M, N, space, value):dp = [[0] * (N + 1) for _ in range(M + 1)]for i in range(1, M + 1):   # first i things consideredfor j in range(1, N + 1): # bag has N spaceif j >= space[i - 1]:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - space[i - 1]] + value[i - 1])else:dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])return dp[M][N]M, N = [int(x) for x in input().split()]
space = [int(x) for x in input().split()]
value = [int(x) for x in input().split()]
solution = Solution()
print(solution.bag(M, N, space, value))

class Solution:def canPartition(self, nums: List[int]) -> bool:@cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）def dfs(i: int, j: int) -> bool:if i < 0:return j == 0return j >= nums[i] and dfs(i - 1, j - nums[i]) or dfs(i - 1, j)s = sum(nums)return s % 2 == 0 and dfs(len(nums) - 1, s // 2)