跳至主要內容

Knapsack

Someone大约 16 分钟Algorithmalgorithmdp

概览

背包问题可以大致分为三类,分别是:

  1. 背包组合问题
  2. True/False 问题
  3. 最大最小问题

其基础的背包问题一般由两个模型演变而来:

  1. 0-1 背包问题
  2. 完全背包问题

本文先研究 0-1 背包和完全背包,而后对其他问题进行研究。

例题索引

0-1 背包

问题类型递推公式备注
例题 LC474:1和00-1 背包最大最小值问题dp[i] = max(dp[i], dp[i-num] + 1)两个背包
例题 LC416:分割等和子集0-1 背包True/False问题dp[i] = dp[i] or dp[i - num]
例题 LC494:目标和0-1 背包组合问题dp[i] += dp[i - num]
例题 LC1049:最后一块石头的重量 III0-1 背包最大最小值问题dp[i] = max(dp[i], dp[i-stone] + stone)

完全背包

问题类型递推公式备注
例题 LC322:零钱兑换完全背包最大最小值问题dp[i] = min(dp[i], dp[i - coin] + 1)
例题 LC279:完全平方数完全背包最大最小值问题dp[i] = min(dp[i], dp[i - num] + 1)
例题 LC518:零钱兑换2完全背包组合问题dp[i] += dp[i - coin]
例题 LC377:组合总数 IV完全背包组合问题dp[i] += dp[i - num]考虑顺序,target 放在外循环
例题 LC139:单词拆分完全背包 True/False问题dp[i] = dp[i] or dp[i - len(word)]考虑顺序

0-1 背包

0-1 背包问题比较简单,其特点是每种物品仅有一件,可以选择放或者不放。求解将哪些物品装入背包可使价值总和最大。

递推公式

F(i,v)F(i, v) 是前 ii 件物品恰放入一个容量为 vv 的背包可以获得的最大价值,其状态转移方程如下所示:

F[i,v]=max(f[i1,v],f[i1,vCi]+Wi)F[i,v] = max(f[i-1, v], f[i-1, v-C_i] + W_i)

这个递推公式表示在只考虑 将第 ii 件物品放入容量为 vv 的背包中 这个子问题,可以包含两种情况:

  1. 不放第 ii 件物品,问题等价于 i1i-1 件物品放入容量为 vv 的背包中
    1. 放第 ii 件物品,问题等价于 i1i-1 件物品放入剩下容量为 vCiv - C_i 的背包中,再加上放第 ii 件物品的重量 WiW_i

例题 经典背包问题

我们首先要会求解经典背包问题,举例来说:

背包容量:size = 90

每个物品的重量:costs = [71, 69, 1]

每个物品的价值:values = [100, 1, 2]

我们要求解在装更可能多的物品的条件下,使得背包内物品价值的总值最大。

我们使用二维 dp 可以写出如下代码:

class Solution:
    def solution(self, weights, values, size):
        if not size:
            return 0

        n = len(weights)
        # 我们定义 dp 数组 dp[i][w], 对于前 i 个物品,当前背包容量为 w,可以装的最大价值是 dp[i][w]
        dp = [[0] * (size + 1) for _ in range(n)]
        # 循环中遍历物品
        for i in range(1, n):
            # 内层循环遍历背包容量
            # for j in range(size + 1) 等同
            for j in range(size, weights[i] - 1, -1):
                # 当前背包装不下
                if weights[i] > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i])
        return dp[n - 1][size]

在上述代码中,我们踩了几个坑:

  1. 二维 DP 数组的定义,dp = [[0] * (size + 1) for _ in range(n)]size + 1 表示列,n 表示行。

    🆚🆚🆚🆚🆚 如果这样比较难记忆,不如直接使用 numpy 去定义,非常方便:dp = np.zeros(shape=(n, size + 1)).

  2. 对于 dp 数组的定义,我们可以理解为:dp[i][j] 的含义为前 i 个物品,当前背包可用容量为 j,当前装下来的总价值

  3. 对于递推公式,是一个经典的递推,不过多解释

  4. ❗🔴🔴🔴 有一点需要特别注意,那就是两重 for 循环的遍历细节。

    1. 第一重从 1 开始正向遍历
    2. 第二重遍历是和背包的总容量有关的,我们从 0 开始遍历到背包的容量为止;我们也可以从背包的容量遍历到当前要放的物品的重量停止,因为再往下就没有意义了。这两种遍历方式在本题中都是 OK 的。

🧡💛💚💙 优化

我们靠二维 DP 的方法求解,加深理解以后,我们可以套公式写出一维 DP 的求解,套用公式的要点在于:

  1. 0-1 背包倒着循环,不考虑物品顺序,物品循环放在外侧
  2. 求解的是最大最小值问题,递推公式dp[i] = max(dp[i], dp[i-num] + 1)
    def solution2(self, weights, values, size):
        if not size:
            return 0

        # 我们拿容量去定义 dp
        dp = [0] + [0] * size

        # 按照背包问题的套路,遍历物品
        for idx, weight in enumerate(weights):
            for i in range(size, weight - 1, -1):
                dp[i] = max(dp[i], dp[i - weight] + values[idx])

        return dp[-1]

如此,我们就进行了统一。

例题 LC474:1和0

474. 一和零open in new window

问题分析:给你一个二进制字符串数组 strs 和两个整数 mn 。请你找出并返回 strs 的最大子集的大小,该子集中最多有 m0n1 。如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

输入:strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

输出:4

解释:最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ,因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

初看这道题较难理解,需要翻译一下,给定 mn,表示背包中最多有 5 个 0 和 3 个 1 -- target,要求是子集,则表示不能重复选 -- 0-1 背包。

这就是 最大最小值的 0-1 背包问题

求解代码如下所示,掌握几个关键点:

  1. 0-1 背包倒着循环。为什么要倒着循环?这是因为我们的递推公式中使用到了 i1i-1 这个中间状态,倒着循环能够保证在推 F[i,v]F[i,v] 的时候能够取用 F[i1,v]F[i-1, v] 的值。
  2. 背包问题外层循环物体、内层循环容量。
  3. 最大最小问题的递推公式。
  4. 状态转移数组初始化的时候初始化为 0
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        if not strs:
            return 0
         dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 遍历 nums
        for s in strs: 
            zero = s.count('0')
            one = s.count('1')
            # 0-1 背包从后往前
            for i in range(m, zero - 1, -1):
                for j in range(n, one - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1)

        return dp[m][n] 

总结来说,这道题目并不是最典型的 0 - 1 背包问题,普通的 0-1 背包问题只有一种容量,但是该背包问题存在 0 和 1 两种容量,每个物品(字符串)均需要分别占用 0 和 1 的若干容量,并且所有物品的价值均为 1。是一个较为典型的二维动态规划问题。

上述代码是经过了状态压缩后的结果,如果不考虑状态压缩的话,可以定义三维 dp,state: dp[i][j][k],i 可以表示选择的物品为前 i 个,j 和 k 分别表示背包 0 和背包 1 的数量限制。在递推过程中,最外循环 i 对应的最新的值,dp[i][j][k] = max(dp[i-1][j-zeros][k-ones]+1, dp[i-1][j][k]),将第一维压缩后便得到和代码相同的递推公式。

例题 LC 416:分割等和子集

416. 分割等和子集open in new window

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

示例 1:

输入:nums = [1,5,11,5]

输出:true

解释:数组可以分割成 [1, 5, 5] 和 [11] 。

分析题目可知:

  1. 0-1 背包问题,循环倒着来
  2. Trur/False 问题,递推公式为:dp[i] = d[i] or dp[i -num]

该题目的要求可以理解为:从背包中找若干个物品,其价值和正好为背包容量的一半。

代码如下:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if not nums:
            return False

        if sum(nums) % 2 == 1:
            return False

        left_target = sum(nums) // 2
        dp = [True] + [False] * left_target
        for num in nums:
            for i in range(left_target, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]

        return dp[left_target]

例题 LC 494:目标和

494. 目标和open in new window

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :

例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1:

输入:nums = [1,1,1,1,1], target = 3

输出:5

解释:一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

分析题目可知:

  1. 0-1 背包问题,循环倒着来
  2. 背包组合问题,递推公式:dp[i] += dp[i-num]

该题目给出了目标和,可以根据这个条件求解出背包的目标,进而写出代码。需要找出的 目标 为(数组的和 + target) // 2。

证明过程为:全部的可分为 +, -,分左右,左右的和为 left + right = sum(nums),要的 target = left - right,相加可得 2 * left = sum(nums) + target, 由于 target 肯定有解,left * 2 则必须是偶数。

代码如下:

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        if target > sum(nums):
            return 0
        left_target = (sum(nums) + target) // 2
        if (sum(nums) + target) % 2 == 1:
            return 0

        # 组合问题解 dp[i] += dp[i - num]
        dp = [1] + [0] * left_target
        for num in nums:
            for i in range(left_target, num - 1, -1):
                dp[i] += dp[i - num]

        return dp[left_target]

LC1049 最后一块石头的重量 III

https://leetcode-cn.com/problems/last-stone-weight-ii/open in new window

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。

分析:这是一道比较隐晦的 0-1 背包问题,其 target 值是石头总重量的一半。

0-1 背包倒着来,最大最小递推公式用 max!

代码如下:

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        left_target = sum(stones) // 2
        dp = [0] + [0] * left_target

        for stone in stones:
            for i in range(left_target, stone - 1, -1):
                dp[i] = max(dp[i], dp[i - stone] + stone)

        return sum(stones) - 2 * dp[left_target]

总结

对比而言,0-1 一维背包的实现方式是:

def zero_one_pack(F, C, W):
    # 倒着来
    for v <- V to C:
        F[v] <- max(F[v], F[v - C] + W)

其中 C 表示某个物体的容量,W 表示其价值。

0-1 背包的伪代码可以为:

F[0..V] <- 0
for i <- 1 to N
	zero_one_pack(Fi, Ci, Wi)
  • 0-1背包倒着来

完全背包

不同于 0-1背包,完全背包中的每种物品都有无限件可以用,求解:将哪些物品装入背包,可使这些物品的耗费的费用总 和不超过背包容量,且价值总和最大。

递推公式

完全背包的递推公式和 0-1 背包十分相似,不同的点仅在于:

  1. 完全背包的内层循环是正着来的。

要解释这个原因,就需要一个推导的过程,其是由 0-1背包推导而来的,其递推公式 F[i,v]=maxF[i1,vkCi]+kWi0kCivF[i, v] = max{F[i − 1, v − kCi] + kWi | 0 ≤ kCi ≤ v},本质上和 0-1 背包相同。

例题 LC 322:零钱兑换

322. 零钱兑换open in new window

编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

从题目中可以得出:

  1. 完全背包问题:正着循环
  2. 最大最小问题,递推公式为:dp[i] = max(dp[i], dp[i-1] + 1)
  3. 不需要考虑顺序,正常循环

题目表述较为简单,直接看代码实现:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if not coins:
            return -1
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)

        return -1 if dp[amount] == float('inf') else dp[amount]

当然也可以改变顺序,这样稍微快一些:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if not coins:
            return -1
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        return -1 if dp[amount] == float('inf') else dp[amount]

通过代码可以看出,这个问题的实现和完全背包也不尽完全相同,其主要不同在于:

  1. 循环的位置变了,现在外层循环了背包,内层循环了物品。这种方式在一定程度上可以提高性能,如果把循环顺序调换回来,代码也是可以通过的。但是上述的循环方式性能较好。
  2. 在代码中进行了一些优化操作,如 if i >= coin 的判断,就是说背包的大小要大于物品才可以进行装载,这样可以提高性能。这一步省略调代码也是可以通过的。
  3. 初始化问题:由于是最小化问题,所以初始化为了 float(inf)

例题 LC 279:完全平方数

279. 完全平方数open in new window

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例 1:

输入:n = 12

输出:3

解释:12 = 4 + 4 + 4

从题目中可以得到信息:

  1. 完全背包问题:正着循环
  2. 最大最小问题,递推公式为:dp[i] = max(dp[i], dp[i-1] + 1)
  3. 不需要考虑顺序,正常循环

代码如下:

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        # 构造物品数组
        nums = [_**2 for _ in range(1, n+1) if _**2 <= n]

        for num in nums:
            for i in range(num, n + 1):
                dp[i] = min(dp[i], dp[i - num] + 1)

        return -1 if dp[-1] == float('inf') else dp[-1]

例题 LC 518:零钱兑换2

518. 零钱兑换 IIopen in new window

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

这个题目和上述例题都是完全背包问题,但是却存在些许不同:

  1. 这是一个完全背包且不考虑顺序的组合问题,外层循环还是和 0-1背包保持一致
  2. 上面题目求解的是凑成目标数量所需要的最小硬币数;改题目求解的是凑成目标数量的硬币组合数
  3. 总结2:上面题目是最大最小问题,该题目是组合问题
  4. 组合问题的递推公式为:dp[i] += dp[i -num]

其代码如下:

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        if not coins:
            return 0
		# 就是 dp[0] = 1
        dp = [1] + [0] * amount

        for coin in coins:
            # 这是一个优化,可以从 1 开始循环,然后判断 i >= coin
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]

        return dp[amount]

例题 LC 377: 组合总数 IV

377. 组合总和 Ⅳopen in new window

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

输入:nums = [1,2,3], target = 4

输出:7

解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。

这是一个经典的考虑顺序的完全背包组合问题,看到这样的问题,首先确定模板:

  1. 完全背包问题:正着循环
  2. 组合问题:递推公式为:dp[i] += dp[i -num]
  3. 考虑顺序,把背包放在外层循环

很轻松写出代码:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        dp = [0] * (target + 1)
        dp[0] = 1
        # 考虑顺序,target 放在外面
        for i in range(1, target + 1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]

        return dp[target]

例题 LC 139:单词拆分

139. 单词拆分open in new window

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]

输出: true

解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

从题目中可以得出信息:

  1. 完全背包问题,(拆分时可以重复使用字典中的单词):正着循环
  2. true/false 问题,递推公式为:dp[i] = dp[i] or dp[i - num]
  3. 考虑顺序,背包在外循环

代码如下:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not wordDict:
            return False
		# dp[0] = True
        dp = [True] + [False] * len(s)

        for i in range(1, len(s) + 1):
            for word in wordDict:
                if i - len(word) >= 0 and s[i - len(word):i] == word:
                    dp[i] = dp[i] or dp[i - len(word)]

        return dp[-1]

总结

完全背包问题的伪代码如下所示:

def CompletePack(F, C, W)
	for v ← C to V
		F[v]max{F[v], f[v − C] + W}
F[0..V ]0
for i ← 1 to N
    for v ← Ci to V
		F[v]max(F[v], F[v − Ci] + Wi)
  • 完全背包正着来
  • 如果与顺序有关,内循环 coins,外循环 target(背包容量在外)

参考文献

一篇文章吃透背包问题!(细致引入+解题模板+例题分析+代码呈现)open in new window