Day42代码随想录动态规划part04：01背包问题的二维数组解法、01背包问题的一维数组解法、416. 分割等和子集

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
• 背包中每一个元素是不可重复放入。

1. 确定dp数组以及下标的含义：dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。 当 dp[target] == target 的时候，背包就装满了。
2. 确定递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3. 初始化：本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。
4. 遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
5. 举例推导：

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