跳转至

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+1dp[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+1dp[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这些完全平方数作为物品,做完全背包。

评论