今日任务：
1）01背包问题理论基础(卡码网：46. 携带研究材料)
2）01背包问题滚动数组(卡码网：46. 携带研究材料)
3）416. 分割等和子集
4）复习day11
卡码网：46. 携带研究材料
题目链接：46. 携带研究材料（第六期模拟笔试） (kamacoder.com)
题目描述 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。 小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。 输入描述 第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。 第二行包含 M 个正整数，代表每种研究材料的所占空间。 第三行包含 M 个正整数，代表每种研究材料的价值。 输出描述 输出一个整数，代表小明能够携带的研究材料的最大价值。 输入示例 6 1 2 2 3 1 5 2 2 3 1 5 4 3 输出示例 5 提示信息 小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。 数据范围： 1 <= N <= 5000 1 <= M <= 5000 研究材料占用空间和价值都小于等于 1000
文章讲解：代码随想录 (programmercarl.com)
视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法哔哩哔哩bilibili
思路：
当解决背包问题时，我们可以使用动态规划来求解。动态规划的思想是将原问题分解成若干个子问题，先求解子问题，然后由子问题的解得到原问题的解。对于背包问题，我们可以定义一个二维数组 dp，其中 dp[i][j] 表示背包容量为 j 时，前 i 个物品能够获得的最大价值。接着，我们根据状态转移方程来填充 dp 数组：
- 如果当前物品的重量大于当前背包容量 j，则无法选择该物品，因此继承上一行的最大价值：dp[i][j] = dp[i-1][j]。
- 否则，当前物品可以选择放入或不放入背包。如果选择放入，则背包的容量减少，价值增加；如果选择不放入，则背包的容量不变，价值不增加。我们选择这两种方案中的价值较大者：dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j - weight[i]])。
最终，我们返回 dp 数组最后一行最后一列的值，即为所求解。
def test_1_wei_bag_problem1(weight, value, bagweight):
# 创建一个二维数组 dp，用于存储背包容量为 j 时，前 i 个物品能够获得的最大价值
dp = [[0]*(bagweight+1) for _ in range(len(weight)+1)]
# 将 weight 和 value 数组插入 0，方便后续计算
weight.insert(0,0)
value.insert(0,0)
# 动态规划过程，填充 dp 数组
for i in range(1,len(weight)):
for j in range(1,bagweight+1):
# 如果当前物品的重量大于当前背包容量 j，则无法选择该物品，直接继承上一行的最大价值
if j < weight[i]:
dp[i][j] = dp[i-1][j]
else:
# 否则，可以选择放入或不放入当前物品，选择其中价值较大的一种方案
dp[i][j] = max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]])
# 返回最终结果，即 dp 数组最后一行最后一列的值
return dp[-1][-1]
if __name__ == "__main__":
# 获取研究材料的种类 M 和小明的行李空间 N
_, bagweight = map(int, input().split())
# 获取每种研究材料的空间和价值
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
# 调用函数计算最大价值并输出结果
result = test_1_wei_bag_problem1(weight, value, bagweight)
print(result)刚才我们是采用二维数组实现，这一题，我们还能采用一维数组实现，就是不断更新一行数组即可
文章讲解：代码随想录 (programmercarl.com)
视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！哔哩哔哩bilibili
思路：
- 创建一个一维数组
dp，用于存储当前背包容量下的最大价值，初始值全部设为0。- 遍历每种研究材料，对于每种材料都进行以下操作：
- 从后向前遍历一维数组
dp，因为当前物品的选择可能会受到之前物品的影响，所以从后向前遍历能够保证只考虑当前物品的放入与不放入，不受之前物品的影响。- 对于每个背包容量
j，如果当前背包容量j大于等于当前物品的重量weight[i]，则可以选择放入当前物品。比较放入当前物品与不放入当前物品的价值大小，取较大者更新dp[j]。- 返回数组
dp中最后一个元素，即能够携带的研究材料的最大价值。
def test_2_wei_bag_problem1(weight, value, bagweight):
# 创建一维数组用于存储当前背包容量下的最大价值
dp = [0] * (bagweight + 1)
# 遍历每种研究材料
for i in range(len(weight)):
# 从后向前遍历一维数组 dp，更新 dp 中的值
for j in range(bagweight, weight[i] - 1, -1):
# 如果当前背包容量 j 大于等于当前物品的重量 weight[i]，
# 则可以选择放入当前物品，比较放入当前物品与不放入当前物品的价值大小，取较大者更新 dp[j]
dp[j] = max(dp[j], value[i] + dp[j - weight[i]])
# 返回能够携带的研究材料的最大价值
return dp[-1]
if __name__ == "__main__":
# 获取研究材料的种类 M 和小明的行李空间 N
_, bagweight = map(int, input().split())
# 获取每种研究材料的空间和价值
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
# 调用函数计算最大价值并输出结果
result = test_2_wei_bag_problem1(weight, value, bagweight)
print(result)416. 分割等和子集
题目链接：416. 分割等和子集 - 力扣（LeetCode）
题目难易：中等 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集. 提示： 1 <= nums.length <= 200 1 <= nums[i] <= 100
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集哔哩哔哩bilibili
思路：
1.判断是否能够平分数组： 首先，计算数组的总和，如果总和为奇数，则无法平分成两个子集，直接返回 False；如果总和为偶数，则将目标值定为总和的一半。
2.动态规划数组初始化： 创建一个动态规划数组
dp，其长度为目标值加 1，初始化为0，表示每个和都无法凑成。
3.动态规划更新： 遍历数组中的每个元素，逆序遍历动态规划数组，更新动态规划数组中每个位置的值，如果当前位置的值能够凑成当前和，则更新为当前和的最大值。
4.判断最终结果： 最后判断动态规划数组中的目标值是否等于目标值本身，如果是，则说明存在一个子集的和等于目标值，返回 True，否则返回 False。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
sum_ = sum(nums)
# 如果总和为奇数，无法平分成两个子集，为偶数则将目标定为总和的一半
if sum_ % 2 != 0 :
return False
target = sum_//2
dp = [0]*(target+1)
# 开始 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
# 比较巧的方法
def canPartition2(self, nums: List[int]) -> bool:
sum_ = sum(nums)
# 如果总和为奇数，无法平分成两个子集，为偶数则将目标定为总和的一半
if sum_ % 2 != 0:
return False
target = sum_ // 2
# 动态规划数组，dp[i] 表示是否可以用数组中的元素组成和为 i
dp = [False] * (target + 1)
dp[0] = True # 和为 0 总是可以组成
# 遍历数组中的每个数字
for num in nums:
# 从后往前更新 dp 数组，防止重复利用当前数字
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num] # 当前和为 i 的情况取决于之前是否能凑出 i - num 的情况
return dp[target]
