Day42 动态规划part03-01背包问题
01背包问题的二维数组解法
01背包问题定义：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
暴力解法：回溯法，枚举所有情况，每个物品是取与不取两个状态
二维数组方法
- dp数组的含义：二维dp[i][j]数组：[0,i]之间的物品任取，放入容量为j的背包里
- 递推公式：dp[i][j] 最后求的是两种情况的最大价值max
- (1)不放物品i，最大价值是dp[i-1][j];
- (2)放物品i, dp[i-1][j-weight[i]] + value[i];
- 初始化：一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
- dp[i][0]：首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]=0，无论是选取哪些物品，背包价值总和一定为0。
- dp[0][i]：根据状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。dp[0][j]，当j<weight[0]时为0，j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
- 其他下标： 从递推公式中看出，其他下标初始为什么数值都可以，因为都会被覆盖。
- 遍历顺序：先遍历物品还是先遍历容量都可以
m,n = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
# print(m,n)
dp = [[0]*(n+1) for _ in range(m)]
# 初始化，dp[i][0]本身就都是0了，只需要初始dp[0][i]
for i in range(n+1):
if i >= weight[0]:
dp[0][i] = value[0]
# print(dp)
for i in range(1, m): #遍历物品
for j in range(1, n+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)
max_value = dp[m-1][n]
print(max_value)
01背包问题的一维数组解法
一维数组方法：核心想法，当前层i都是由上一层的i-1推导出来的，我们可以把上一层的拷贝到当前层进行计算，然后再用当前层的新计算值覆盖i+1层
- dp数组含义：dp[j]容量为j的背包所能装的最大价值为dp[j]
- 递归公式：dp[j]=max(dp[j], dp[j- weight[i]] + value[i])；dp[j]不放物品i，从上一层拷贝下来的
- 初始化：dp[0]背包容量为0的最大价值为0，其余也都初始化成0（非负的最小值）是因为如果初始化成一个大的数求max时可能会有影响
- 遍历顺序：先遍历物品，再遍历背包容量**（倒序），这是因为为了物品i只被放入1次**。因为二维dp数组不受上一层的影响，而1维是每次重复利用的。
- 如果正序遍历：dp[1] = dp[1 - weight[0]] + value[0] = 15，dp[2] = dp[2 - weight[0]] + value[0] = 30，此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
- 倒序就是先算dp[2]：dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0），dp[1] = dp[1 - weight[0]] + value[0] = 15。所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
- 对于一维dp只能先遍历物品，再遍历背包。背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
- 推导：物品0重量1价值15，物品1重量3价值20，物品2重量4价值30
题目：卡码网46：46. 携带研究材料（第六期模拟笔试） (kamacoder.com)
m,n = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
# print(m,n)
dp = [0]*(n+1)
# 初始化，dp[i]本身就都是0了
for i in range(m): #遍历物品
for j in range(n, weight[i]-1, -1): #遍历空间
#注意这里因为是倒叙，所以是从n开始！不是n+1
# print(i,j, weight[i])
dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
# pass
# print(dp)
max_value = dp[n]
print(max_value)
416. 分割等和子集
leetcode题目链接：416. 分割等和子集 - 力扣（LeetCode）
题意：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1:
- 输入: [1, 5, 11, 5]
- 输出: true
- 解释: 数组可以分割成 [1, 5, 5] 和 [11].
思路：只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。因为每个元素只能使用1次，所以是0-1背包问题
只有确定了如下四点，才能把01背包问题套到本题上来。
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值；也就是之前的weight就是此时的value
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。dp[sum/2] == sum/2
- 背包中每一个元素是不可重复放入。
- 确定dp数组以及下标的含义：dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。 当 dp[target] == target 的时候，背包就装满了。
- 确定递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
- 初始化：本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
- 遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
- 举例推导：
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
target = sum(nums)//2
dp = [0]*(target+1)
if sum(nums)%2 != 0:
return False
for i in range(n):
# print(dp)
for j in range(target, nums[i]-1, -1):
dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
# print(dp)
if dp[target] == target:
return True
else:
return False
