第九章 动态规划part04

本文主要是介绍第九章 动态规划part04，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先要搞懂0-1背包问题

搞清楚二维和一维的dp数组的不同含义

while True:try:m,n = map(int,input().split())space = list(map(int,input().split()))value = list(map(int,input().split()))dp = [0]*(n+1)for i in range(m):for j in range(n,space[i]-1,-1):dp[j] = max(dp[j],dp[j-space[i]]+value[i])print(dp[-1])except EOFError:break

416. 分割等和子集

接下来是一道应用，这道应用十分的灵活，感觉背包问题可以应用到很多不同的领域里去

class Solution:def canPartition(self, nums: List[int]) -> bool:sumN = sum(nums) // 2if sum(nums) % 2 != 0:return Falsedp = [0] * (sumN+1)for i in range(len(nums)):for j in range(sumN,nums[i]-1,-1):dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])return dp[sumN] == sumN

这篇关于第九章 动态规划part04的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---