代码随想录算法训练营day35 | 0-1背包理论基础、416. 分割等和子集

碎碎念：加油！！
参考：

0-1背包理论基础

几类背包的区别：
0-1背包的每种物品只有一个
完全背包的每种物品有无限个
多重背包的每种物品的个数各不相同

当前层是由上一层推导来的，所以可以直接把上一层拷贝 到当前层，然后直接在当前层进行计算，把新的值覆盖到当前层中。

用一维dp数组实现01背包-动态规划五部曲：

1. 确定dp数组以及下标的含义：dp[j]，容量为j的背包所背的最大价值。
2. 确定递推公式：不放物品i，dp[j]；放物品i，dp[j-weight[i]] + value[i]。
   dp[j] = max(dp[j], dp[j-weight[i]] + value[i])。
3. dp数组的初始化：dp[0]=0，递推公式里是取最大值，所以初始化应该初始化为非负数的最小值，所以可以把dp数组全部初始化为0。
4. 确定遍历顺序：两层for循环，第一层for循环遍历物品，第二层for循环遍历背包。遍历背包的时候倒序遍历。倒序遍历是为了保证每一个物品的值只被添加一次。
5. 打印dp数组：主要用来debug。

416. 分割等和子集

题目链接

思想

动态规划五部曲：

1. 确定dp数组以及下标的含义：dp[j]，容量为j的背包所背的最大价值。
2. 确定递推公式：dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])。
3. dp数组的初始化：dp[0]=0，递推公式里是取最大值，所以初始化应该初始化为非负数的最小值，所以可以把dp数组全部初始化为0。
4. 确定遍历顺序：两层for循环，第一层for循环遍历物品，第二层for循环遍历背包。遍历背包的时候倒序遍历。倒序遍历是为了保证每一个物品的值只被添加一次。
5. 打印dp数组：主要用来debug。

题解

// cpp
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[target] == target) return true;
        return false;
    }
};

# python
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        _sum = 0
        dp = [0] * 10001
        for num in nums:
            _sum += num
        if _sum % 2 == 1:
            return False
        target = _sum // 2

        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = max(dp[j], dp[j-num] + num)
        
        if dp[target] == target:
            return True
        return False

反思

注意遍历物品和背包的顺序，注意遍历背包的时候要倒序遍历，防止重复使用同一个数字。