跳转至

LeetCode 背包问题

本文是我学习背包问题的一些总结。

算法题算是我求职路上的一道坎，我没有数据结构与算法的学习经验，但许多笔试都需要考算法题。我花了两天时间系统学习动态规划中的背包问题，希望能让自己再次遇到这类问题时不再畏惧。之前以为只有计算机系同学才能做出的题目，我也能自己做出来了，这就是学习的收获。

背包问题是指有一个固定容量为c的背包，以及一组物品，每个物品都有自己的重量w[i]和价值p[i]。在不超过背包容量的前提下，选择不同的物品装入背包，使得装入背包中的物品总价值最大。

big-picture

01 背包

在 01 背包问题中，每个物品只能用一次。

可以用 二维数组 或 一维数组 来解答，后者的空间复杂度更低，因此我们后续都使用一维数组。

总结

使用一维数组求解 01 背包问题时，必须先遍历物品，再遍历背包容量，并且遍历背包容量时需要 倒序 。

为什么要倒序？一个比较好的解释是（来源：【带你学透 01 背包问题（滚动数组篇） | 从此对背包问题不再迷茫！】 ）：

image-20230331103809982

问题角度 1：给定背包容量，最多能装多少价值的物品？

这是最基础的问题角度，步骤如下：

  • 确定dp数组的定义。

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

  • 初始化dp数组。它的 长度为c+1，初始值都为0 。
Python
dp = [0 for _ in range(c + 1)]
  • 遍历所有物品，倒序遍历背包容量（从dp[c]遍历到dp[w[i]]，因为小于w[i]的背包容量是不会发生变化的）。
Python
# 遍历物品
for i in range(len(w)):
    # 倒序遍历背包容量
    for j in range(c, w[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - w[i]] + p[i])

由此角度衍生出的问题

  • 416. 分割等和子集 是求给定背包容量，能不能装满这个背包。
  • 1049. 最后一块石头的重量 II 是求给定背包容量，尽可能装，最多能装多少。
  • 0474. 一和零 是求给定背包容量，装满背包最多有多少个物品。注意背包是二维的，可以理解为：背包最多能装 m 个 0 个 n 个 1。再将每个物品的价值抽象为 1，我们需要最大化背包里面的物品个数，也就是最大化背包的价值。

问题角度 2：给定背包容量，装满背包有多少种方法？

  • 确定dp数组以及下标的含义。

dp[j]表示：填满j（包括j）这么大容积的背包，有dp[j]种方法。

  • 初始化dp数组。它的 长度为c+1，dp[0] = 1，其他初始值都为0 。

在初始化的时候 dp[0] 一定要初始化为 1，因为 dp[0]是在公式中一切递推结果的起源，如果 dp[0] 是 0 的话，之后所有递推结果将都是 0。

Python
dp = [0 for _ in range(c + 1)]
dp[0] = 1
  • 遍历所有物品，倒序遍历背包容量（从dp[c]遍历到dp[w[i]]，因为小于w[i]的背包容量是不会发生变化的）。
Python
# 遍历物品
for i in range(len(w)):
    # 倒序遍历背包容量
    for j in range(c, w[i] - 1, -1):
        dp[j] = dp[j] + dp[j - w[i]]

这个递归方程的意思是，如果我们要用若干个元素组成和为 j 的方案数，那么有两种选择：不选第 i 个元素或者选第 i 个元素。如果不选第 i 个元素，那么原来已经有的dp[j]种方案数就不变；如果选第 i 个元素，那么剩下要组成和为 j - w[i]的方案数就等于 dp[j - w[i]]。所以两种选择相加就是新的 dp[j]。

由此角度衍生出的问题

  • 494. 目标和 是求给定背包容量，装满背包有多少种方法。

完全背包

完全背包的大部分步骤与 01 背包完全一致，只需要在遍历背包容量时将倒序遍历改为正序遍历即可，因为每个物品可以无限次使用。

问题角度 1：给定背包容量，最多能装多少价值的物品？

Python
dp = [0 for _ in range(c + 1)]
# 遍历物品
for i in range(len(w)):
    # 顺序遍历背包容量
    for j in range(w[i], c + 1):
        dp[j] = max(dp[j], dp[j - w[i]] + p[i])

问题角度 2：给定背包容量，装满背包有多少种方法？（求组合数）

Python
dp = [0 for _ in range(c + 1)]
dp[0] = 1
# 遍历物品
for i in range(len(w)):
    # 顺序遍历背包容量
    for j in range(w[i], c + 1):
        dp[j] = dp[j] + dp[j - w[i]]

由此角度衍生出的问题

  • 518. 零钱兑换 II 是求给定背包容量，装满背包有多少种方法（求组合数）。

问题角度 3：给定背包容量，装满背包有多少种方法？（求排列数）

求排列数时，需要将背包容量放在外循环，将物品放在内循环。

Python
dp = [0 for _ in range(c + 1)]
dp[0] = 1
# 遍历背包容量
for j in range(c + 1):
    # 遍历物品
    for i in range(len(w)):
        if w[i] <= j:
            dp[j] = dp[j] + dp[j - w[i]]

由此角度衍生出的问题

  • 0377. 组合总和 Ⅳ 是求给定背包容量，装满背包有多少种方法（求排列数））。
  • 70. 爬楼梯 给定总台阶数，每次可以爬 1 阶或 2 阶，求一共有多少种爬楼梯的方法。这道题当然可以用简单的斐波那契数列进行计算，但如果每次可以爬的台阶数太多，就更适合用完全背包问题求解，两层循环不断累加即可。

总结

如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。

如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。

问题角度 4：给定背包容量，装满背包最少需要多少件不同的物品？

  • 确定dp数组的定义。凑足总额为 j 所需钱币的最少个数为 dp[j]

    在一维dp数组中，dp[j]表示：容量为j的背包，所背的不同物品数量最小为dp[j]。

  • 初始化dp数组。它的 长度为c+1，dp[0]初始值为 0，其他初始值都为float("inf")或者c + 1 。这里可以用float("inf")代表无穷大；也可以用c + 1，因为若硬币的最小价值是 1，则不可能需要c+1个硬币来组成c的价值。

    Python
    dp = [float("inf") for _ in range(c + 1)]
dp[0] = 0

  • 遍历所有物品，正序遍历背包容量。

    递归逻辑是：要么不加入新的物品，需要dp[j]件物品才能凑成 j的金额；要么加入新的物品，需要dp[j - w[i]] + 1)件物品才能凑成 j的金额。取两者 最小值 即可。

    Python
    # 遍历物品
for i in range(len(w)):
    # 遍历背包容量
    for j in range(w[i], c + 1):
        dp[j] = min(dp[j], dp[j - w[i]] + 1)

由此角度衍生出的问题

  • 322. 零钱兑换 是求给定背包容量，装满背包最少需要多少件不同的物品。
  • 279.完全平方数 是求给定背包容量，装满背包最少需要多少件不同的物品。需要将待求和的整数 n 看成背包容量，再用\(1^2\)、\(2^2\)、\(3^2\)一直到(int(n**0.5)+1)**2这些完全平方数作为物品，做完全背包。

评论