正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。?
如果是直接从来没听过背包问题，可以先看文字讲解慢慢了解?这是干什么的。
如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。?
背包问题，力扣上没有原题，大家先了解理论，今天就安排一道具体题目。?
?详细布置
?
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背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_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数组也是比二维数组好理解一些。
用回溯写了一下，不过超时了，不知道是不是对的。
class Solution(object):
def canPartition(self, nums):
nums.sort()
sum_total=sum(nums)
if sum_total%2!=0:
return False
result=[]
return self.beakstrings(nums,[],result,0,0,sum_total)
def beakstrings(self,nums,path,result,startindex,total,sum_total):
if result:
return True
if total==sum_total//2:
result.append(path[:])
return True
if total>sum_total//2:
return
for 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:
break
if result:
return True
else:
return Falseclass Solution(object):
def canPartition(self, nums):
total=sum(nums)
if total%2!=0:
return False
target=total//2
dp=[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背包的写法没什么区别了。