正式开始背包问题，背包问题还是挺难的，虽然看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。
如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。?
背包问题，力扣上没有原题，先了解理论，今天一道具体题目?
对于二维dp数组实现的01背包，其遍历顺序的两层for循环可以颠倒，但一维dp数组不行
上一层可以重复利用，直接拷贝到当前层，在进行计算
可以去卡码网第46题?(opens new window)去练习
1、用二维数组解决01背包问题————再问两个for循环是否能够颠倒顺序，再问为什么二维数组不用从后向前遍历，而从前向后遍历就可以
2、用一维数组解决01背包问题————再问两个for循环是否能够颠倒顺序、这个for循环为什么从后向前遍历，为什么不能从前向后遍历
本题是?01背包的应用类题目
class Solution:
def canPartition(self, nums: List[int]) -> bool:
_sum = 0
# dp[i]中的i表示背包内总和
# 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
# 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
dp = [0] * 10001
for num in nums:
_sum += num
# 也可以使用内置函数一步求和
# _sum = sum(nums)
if _sum % 2 == 1:
return False
target = _sum // 2
# 开始 0-1背包
for num in nums:
for j in range(target, num - 1, -1): # 每一个元素一定是不可重复放入，所以从大到小遍历
dp[j] = max(dp[j], dp[j - num] + num)
# 集合中的元素正好可以凑成总和target
if dp[target] == target:
return True
return False