背包问题总结

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是value[i] ，且每件物品只能使用一次，求解将哪些物品装入背包里物品价值总和最大，最大为多少？

经典题目

分割等和子集

# 示例：
"""
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
"""
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_nums = sum(nums)  # 统计sum
        if sum_nums % 2 == 1:
            return False
        target = sum_nums // 2  # 此时背包大小为target
        dp = [False] * (target + 1)
        dp[0] = True
        for num in nums:
            if num > target:
                return False
            for j in range(target, num-1, -1):
                dp[j] = dp[j-num] | dp[j]  # 判断是否可以实现当前数值
        return dp[-1]

思路

• 先将题目进行理解和转换：
• 元素和为奇数时一定不能成立，返回False；
• 将问题转化为显而易见的背包问题，即背包大小 target=sum/2，nums中元素可表示为重量

• 利用背包问题的解法进行求解：
• 本题相当于背包里放入物品，理解为物品i的重量是nums[i]，其价值也是nums[i]；
• 递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])；
• 确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历；

背包递推公式

• 动态规划：416.分割等和子集(opens new window)

• 动态规划：1049.最后一块石头的重量 II(opens new window)

• 动态规划：494.目标和(opens new window)

• 动态规划：518. 零钱兑换 II(opens new window)

• 动态规划：377.组合总和Ⅳ(opens new window)

• 动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

• 动态规划：474.一和零(opens new window)

• 动态规划：322.零钱兑换(opens new window)

• 动态规划：279.完全平方数(opens new window)

遍历顺序

01背包

完全背包

总结

• 递推公式可以参考总结地几种公式进行套用，但关键还是在于对于题目地理解来快速确定递推公式；

• 遍历顺序：遍历顺序通常需要考虑两个方面的遍历；
• 先遍历物品/背包：针对不同的问题需要考虑不同的遍历顺序；针对01背包中一维/二维数组的选择页需要考虑不同的遍历顺序；
• 从大到小/从小到大遍历：其实特殊情况就在于01背包中一维数组实现时需要进行从大到小遍历，其余都从小到大遍历即可；

• LeetCode中题型多为中等，主要因为题解无外乎几种情况，可以一一进行分析，掌握后就可以快速解出题目；

参考

代码随想录

代码随想录PDF，代码随想录百度网盘，代码随想录知识星球，代码随想录八股文PDF，代码随想录刷题路线，代码随想录知识星球八股文

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html#_01-%E8%83%8C%E5%8C%85