代码随想录算法训练营DAY41｜背包问题 二维 、背包问题 一维、416. 分割等和子集

背包问题 二维

• 题目链接：背包问题 二维

def bag_weight_problem(n,space,weight,value):dp = [[0 for i in range(space+1)]for j in range(n)]for i in range(weight[0], space+1):dp[0][i]=value[0]for j in range(1, n):for k in range(space+1):if weight[j]>k:dp[j][k]=dp[j-1][k]else:dp[j][k]=max(dp[j-1][k], dp[j-1][k-weight[j]]+value[j])return dp[n-1][space]if __name__ == '__main__':n, space = [int(x) for x in input().split()]weight = [int(x) for x in input().split()]value = [int(x) for x in input().split()]result = bag_weight_problem(n,space,weight,value)print(result)

背包问题 一维

• 题目链接：背包问题 一维

def bag_weight_problem(n,space,weight,value):dp = [0 for i in range(space+1)]for j in range(n):for k in range(space,weight[j]-1,-1):dp[k]=max(dp[k], dp[k-weight[j]]+value[j])return dp[space]if __name__ == '__main__':n, space = [int(x) for x in input().split()]weight = [int(x) for x in input().split()]value = [int(x) for x in input().split()]result = bag_weight_problem(n,space,weight,value)print(result)

416. 分割等和子集

• 题目链接：416. 分割等和子集

class Solution(object):def canPartition(self, nums):""":type nums: List[int]:rtype: bool"""sum_nums = sum(nums)n = len(nums)if sum_nums%2==1:return Falseelse:weight = sum_nums/2dp = [0 for i in range(weight+1)] for i in range(n):if nums[i]>weight:return Falsefor j in range(weight, nums[i]-1, -1):dp[j]=max(dp[j], dp[j-nums[i]]+nums[i])if dp[weight]==weight:return Trueelse:return False