算法随想录第四十二天打卡|01背包问题，你该了解这些！，01背包问题，你该了解这些！ 滚动数组， 416. 分割等和子集
正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。
如果是直接从来没听过背包问题，可以先看文字讲解慢慢了解 这是干什么的。
如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。
背包问题，力扣上没有原题，大家先了解理论，今天就安排一道具体题目。
详细布置
01背包问题 二维
代码随想录
视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili
def test_2_wei_bag_problem1():weight = [1, 3, 4]value = [15, 20, 30]bagweight = 4# 二维数组dp = [[0] * (bagweight + 1) for _ in range(len(weight))]# 初始化for j in range(weight[0], bagweight + 1):dp[0][j] = value[0]# weight数组的大小就是物品个数for i in range(1, len(weight)): # 遍历物品for j in range(bagweight + 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[len(weight) - 1][bagweight])test_2_wei_bag_problem1()
总结
在卡码网的代码提交形式我看不懂，不过01背包的思路我理解了。dp[i][j]中i代表的是从0到i下标的商品，而j表示背包的容量，dp[i][j]表示能达到的最大的价值。
01背包问题 一维
代码随想录
视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili
def test_1_wei_bag_problem():weight = [1, 3, 4]value = [15, 20, 30]bagWeight = 4# 初始化dp = [0] * (bagWeight + 1)for i in range(len(weight)): # 遍历物品for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i])print(dp[bagWeight])test_1_wei_bag_problem()总结
感觉一维遍历和我们前面写的动态规划的问题相似，都是借用前面的值来解决后面的值，这就是把他化成一个个小的问题。之所以会用后序遍历也是因为他会重复使用前面已经使用的背包所以不能用前序遍历，而后序遍历和之前的背包无关。之所以要先遍历物品再遍历背包，是因为反过来的话它只会使用一个物品来填背包。这里的dp数组也是比二维数组好理解一些。
416. 分割等和子集
本题是 01背包的应用类题目
代码随想录
视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili
思路
用回溯写了一下，不过超时了，不知道是不是对的。
class Solution(object):def canPartition(self, nums):nums.sort()sum_total=sum(nums)if sum_total%2!=0:return Falseresult=[]return self.beakstrings(nums,[],result,0,0,sum_total)def beakstrings(self,nums,path,result,startindex,total,sum_total):if result:return Trueif total==sum_total//2:result.append(path[:])return Trueif total>sum_total//2:returnfor i in range(startindex,len(nums)):total+=nums[i]path.append(nums[i])self.beakstrings(nums,path,result,i+1,total,sum_total)path.pop()total-=nums[i]if result:breakif result:return Trueelse:return Falseclass Solution(object):def canPartition(self, nums):total=sum(nums)if total%2!=0:return Falsetarget=total//2dp=[0]*(target+1)for i in nums: #这一层指物品for j in range(target,i-1,-1):dp[j]=max(dp[j],dp[j-i]+i)return dp[-1]==target总结
这题不看答案我是真的想不出来用背包问题来解决的，这把每一个数即看成体积又看成价值的方法还是有点不理解，感觉除了这个不同其他的和01背包的写法没什么区别了。