Posted on Views:

前言

背包问题 (Knapsack problem) 是一种组合优化的 NP (NP-Complete) 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。@百度百科

一般问题： 我们有 nn 件物品和一个容量 (capacity)(capacity) 为 CC 的背包，记第 ii 件物品的重量 (weight)(weight) 为 wiw_i，价值 (value)(value) 为 viv_i，求将哪些物品装入背包可使价值总和最大。

0-1背包： 如果限定每件物品最多只能选取 11 次（即 0 或 10\ 或\ 1 次），则问题称为 0-1背包问题。

完全背包： 如果每件物品最多可以选取无限次，则问题称为 完全背包问题。

假设放入背包中的物品 ii 的数目为 kik_{i}，则上述背包问题在数学上可表达为：

max⁡ ∑i=0n−1 ki⋅vi ,\max \ \sum_{i=0}^{n-1}\ k_{i} \cdot v_{i} \ ,

受限于 s.t.s.t.

∑i=0n−1ki⋅wi⩽C,{ki∈{0,1}⟵ 「0-1背包问题」 ki∈{0,1,2,…,+∞}⟵ 「完全背包问题」 \sum_{i=0}^{n-1} k_{i} \cdot w_{i} \leqslant C, \quad \left\{\begin{array}{lll} k_{i} \in\{0,1\} & \textcolor{red}{\longleftarrow} & \text { 「0-1背包问题」 } \\ k_{i} \in\{0,1,2, \ldots,+\infty\} & \textcolor{red}{\longleftarrow} & \text { 「完全背包问题」 } \end{array}\right.

0-1背包 和 完全背包 是两种最为常见的背包问题，其他类型的背包问题，如多重背包、分组背包等可参考网上的一些资料， 如：《背包问题九讲》（网页版） （PDF版）

拓展：

动态规划 是解决「0−1 背包问题」和「完全背包问题」的标准做法。

1. 「0−1 背包问题」

一般地，我们定义：dp[i][j]dp[i][j] 表示前 ii 件物品放入一个容量为 jj 的背包可以获得的最大价值（每件物品最多放一次），则状态转移过程可表示为：

  • 不选择第 ii 件物品，则问题转化为了前 i−1i-1 件物品放入容量为 jj 的背包中所获得的价值：dp[i][j]=dp[i−1][j]dp[i][j] =dp[i-1][j] ；
  • 选择第 ii 件物品，则问题转化为了前 i−1i-1 件物品放入容量为 j−wij-w_i 的背包中所获得的价值 dp[i−1][j−wi]dp[i-1][j-w_i] 加上要放入的第 ii 件物品的价值 viv_i：dp[i][j]=dp[i−1][j−wi]+vidp[i][j] =dp[i-1][j-w_i] + v_i 。注意，能放入第 ii 件物品的前提为：wi≤jw_i \leq j。

两种情况取较大者即可得到「状态转移方程」为：

dp[i][j]=max⁡{ dp[i−1][j],dp[i−1][j−wi]+vi } .dp[i][j] = \max\left\{ \ dp[i-1][j],\quad dp[i-1][j-w_i] + v_i \ \right\}\ .

2. 「完全背包问题」

类似于「0−1 背包」，但不同的是每件物品有无限个供应：从每件物品的数量来考虑，相关方案已并非取（取 11 件）或不取（取 00 件）两种情况，而是有取 00 件、取 11 件、取 22 件……取 kk 件等很多种。

一般地，我们定义：dp[i][j]dp[i][j] 表示前 ii 件物品放入一个容量为 jj 的背包可以获得的最大价值（每件物品有无限个）。每件物品可以被选择多次，因此 dp[i][j]dp[i][j] 应为以下所有可能方案中的最大值：

  • 第 ii 件物品选 00 个的最大价值 dp[i−1][j]dp[i-1][j] ；
  • 第 ii 件物品选 11 个的最大价值 dp[i−1][j−wi]+vidp[i-1][j-w_i] + v_i ；
  • 第 ii 件物品选 22 个的最大价值 dp[i−1][j−2⋅wi]+2⋅vidp[i-1][j-2⋅w_i] + 2⋅v_i ；
    ……
  • 第 ii 件物品选 kk 个的最大价值 dp[i−1][j−k⋅wi]+k⋅vidp[i-1][j-k⋅w_i] + k⋅v_i 。

注意，第 ii 件物品能放入 kk 件的前提为：k⋅wi≤jk⋅w_i \leq j。

取最大值即可得到「状态转移方程」为：

dp[i][j]=max⁡{ dp[i−1][j−k⋅wi]+k⋅vi } ,0<=k⋅wi<=jdp[i][j] = \max\left\{ \ dp[i-1][j-k\cdot w_i] + k\cdot v_i \ \right\}\ ,\quad 0<=k\cdot w_i<=j

由状态方程可知，我们可以借鉴「0−1 背包」问题的求解方式来解决「完全背包问题」，但对于每件物品而言每次都需要枚举所有可行的物品数目 kk，这无疑会大大增加系统的开销。

事实上，我们可以对上述状态转移方程进行优化，得到更为简洁的表达（见下）。

完全背包问题的状态空间优化

将上述状态转移方程展开可得：

（1）dp[i][j]=max⁡{ dp[i−1][j],dp[i−1][j−wi]+vi, dp[i−1][j−2⋅wi]+2⋅vi, …, dp[i−1][j−k⋅wi]+k⋅vi },0<=k⋅wi<=j（1）dp[i][j] = \max \{ \ dp[i-1][j],\quad \textcolor{red}{dp[i-1][j-w_i] + v_i}, \textcolor{teal}{\ dp[i-1][j-2\cdot w_i] + 2\cdot v_i}, \\ \ …, \ \textcolor{blue}{dp[i-1][j-k\cdot w_i] + k\cdot v_i} \ \} ,\quad 0<=k\cdot w_i<=j

而恰巧的是对于 dp[i][j−wi]dp[i][j-w_i] 我们有：

（2）dp[i][j−wi]=max⁡{ dp[i−1][j−wi], dp[i−1][j−2⋅wi]+vi, …, dp[i−1][j−k⋅wi]+(k−1)⋅vi },wi<=k⋅wi<=j（2）dp[i][j-w_i] = \max \{ \ \textcolor{red}{dp[i-1][j-w_i]}, \ \textcolor{teal}{dp[i-1][j-2\cdot w_i] + v_i}, \quad \quad \quad \quad \quad \\ \ …, \ \textcolor{blue}{dp[i-1][j-k\cdot w_i] + (k-1)\cdot v_i} \ \} ,\quad w_i<=k\cdot w_i<=j

观察发现，（2）式与（1）式中的后 kk 项刚好相差了一个 viv_i，将（2）式代入（1）式可得简化后的「完全背包问题」的「状态转移方程」为：

（3）dp[i][j]=max⁡{ dp[i−1][j],dp[i][j−wi]+vi },0<=wi<=j（3）dp[i][j] = \max \{ \ dp[i-1][j],\quad \textcolor{red}{dp[i]}[j-w_i] + v_i\ \} ,\quad 0<=w_i<=j \quad \quad \quad \quad

⚠️ 注意，式（3）与「0-1 背包问题」的状态转移方程及其相似，差别（以红色标注）在于第二项中的状态转移是来自上一行还是本行。这也决定了具体编程实现时状态更新方式的异同。

对比总结

两种背包问题的状态转移方程对比总结如下：

0−1背包：dp[i][j]=max⁡{ dp[i−1][j],dp[i−1][j−wi]+vi },0<=wi<=j0-1背包：dp[i][j] = \max\left\{ \ dp[i-1][j],\quad \textcolor{red}{dp[i-1]}[j-w_i] + v_i \ \right\},\quad 0<=w_i<=j \quad \quad

完全背包： dp[i][j]=max⁡{ dp[i−1][j],dp[i][j−wi]+vi },0<=wi<=j 完全背包：\ dp[i][j] = \max \{ \ dp[i-1][j],\quad \textcolor{red}{dp[i]}[j-w_i] + v_i\ \} ,\quad 0<=w_i<=j \quad \quad

⚠️ 求最优解的背包问题中，有的题目要求恰好装满背包时的最优解，有的题目则要求不超过背包容量时的最优解。一种区别这两种问法的实现方法是在状态初始化的时候有所不同。[摘自@《背包问题九讲》（网页版） （PDF版）]
初始化的 dpdp 数组事实上就是在背包中没有放入任何物品时的合法状态：

  1. 如果要求恰好装满背包，那么在初始化时 dp[i][0]=0dp[i][0]=0，其它 dp[i][1,2,…,∗]dp[i][1,2,…,*] 均设为 −∞-∞。这是因为此时只有容量为 00 的背包可能被价值为 00 的 nothing “恰好装满”，而其它容量的背包均没有合法的解，属于未定义的状态。
  2. 如果只是要求不超过背包容量而使得背包中的物品价值尽量大，初始化时应将 dp[∗][∗]dp[*][*] 全部设为 00。这是因为对应于任何一个背包，都有一个合法解为 “什么都不装”，价值为 00。

题目分析：

给定一个整数数组 coinscoins，表示不同面额的硬币；以及一个整数 amountamount，表示总金额。本题要求的是在每种硬币的数量是无限的情况下，计算并返回可以凑成总金额所需的 最少的硬币个数 。

每种硬币的数量是无限的，这是一个典型的「完全背包」求最优解问题。对于本题，定义二维数组 dp[i][j]dp[i][j] 表示：从前 ii 个硬币中组成金额 jj 所需最少的硬币数量。

基于题目要求，上述完全背包的状态转移方程可修改为：

优化前：dp[i][j]=min⁡{ dp[i−1][j−k⋅wi]+k } ,0<=k⋅wi<=j优化前：dp[i][j] = \min\left\{ \ dp[i-1][j-k\cdot w_i] + k \ \right\}\ ,\quad 0<=k\cdot w_i<=j \quad\quad

优化后：dp[i][j]=min⁡{ dp[i−1][j],dp[i][j−wi]+1 },0<=wi<=j优化后：dp[i][j] = \min \{ \ dp[i-1][j],\quad \textcolor{red}{dp[i]}[j-w_i] + 1\ \} ,\quad 0<=w_i<=j \quad \quad

对应于对于第 ii 个硬币，选 00、11、22、…、kk 个组成金额 jj 时所对应的最小硬币数目。

初始化时，dp[i][0]=0dp[i][0] = 0，表示从前 ii 个硬币中凑出金额 00 所需要的硬币数目为 00。【不选任何硬币即可得到 00 】
其他不合法的或未定义的状态则可以设置为正无穷或一个不可能取到的较大值。

为便于理解，这里给出从套用「0-1背包问题」到优化的「完全背包问题」的代码，逐层递进。

代码Copy for Markdown

1.【二维DP，三层循环】
动态规划的基础代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        n = len(coins)
        dp = [[amount+1] * (amount+1) for _ in range(n+1)]    # 初始化为一个较大的值，如 +inf 或 amount+1
        for i in range(n+1):    # 合法的初始化
            dp[i][0] = 0
        
        # 完全背包：套用0-1背包【遍历硬币数目k】
        for i in range(1, n+1):                     # 第一层循环：遍历硬币
            for j in range(amount+1):               # 第二层循环：遍历背包
                for k in range(j//coins[i-1]+1):    # 第三层循环：当前硬币coin取k个 (k*coin<=amount)
                    dp[i][j] = min( dp[i][j], dp[i-1][j-k*coins[i-1]] + k )

        ans = dp[n][amount] 
        return ans if ans != amount+1 else -1

仿照「0-1背包」中的空间优化，可将上述代码实现从【二维DP，三层循环】变为【一维DP，三层循环】，即在”第二层循环-遍历背包” 中「倒序遍历」背包容量。可参考拓展中给出的0-1背包问题的题解，如 「416. 分割等和子集」。

2.【二维DP，两层循环】
基于优化后的状态转移方程，可省去第三层循环，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        n = len(coins)
        dp = [[amount+1] * (amount+1) for _ in range(n+1)]    # 初始化为一个较大的值，如 +inf 或 amount+1
        for i in range(n+1):    # 合法的初始化
            dp[i][0] = 0
        
        # 完全背包：优化后的状态转移
        for i in range(1, n+1):             # 第一层循环：遍历硬币
            for j in range(amount+1):       # 第二层循环：遍历背包
                if j < coins[i-1]:          # 容量有限，无法选择第i个硬币
                    dp[i][j] = dp[i-1][j]
                else:                       # 可选择第i个硬币
                    dp[i][j] = min( dp[i-1][j], dp[i][j-coins[i-1]] + 1 )

        ans = dp[n][amount] 
        return ans if ans != amount+1 else -1

3.【一维DP，两层循环】 动态规划的滚动数组优化

在上面的状态转移方程中，每一行的 dp[i][j]dp[i][j] 状态值都只与上一行（正上方）的 dp[i−1][j]dp[i-1][j] 和 本行（左方）的dp[i][j−∗]dp[i][j-*] 状态值有关，因此可基于滚动数组的思想进行对状态空间 dpdp 进行优化而省去第一维度：

dp2[j]=min⁡{ dp[j],dp2[j−wi]+1 },0<=wi<=j\textcolor{red}{dp2}[j] = \min \{ \ dp[j],\quad \textcolor{red}{dp2}[j-w_i] + 1\ \} ,\quad 0<=w_i<=j \quad \quad

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        n = len(coins)
        dp = [amount+1] * (amount+1)    # 初始化为一个较大的值，如 +inf 或 amount+1
        dp[0] = 0        # 合法的初始化
        
        # 完全背包：优化后的状态转移
        for i in range(1, n+1):             # 第一层循环：遍历硬币
            dp2 = [amount+1] * (amount+1)   # 滚动数组
            dp2[0] = 0
            for j in range(amount+1):       # 第二层循环：遍历背包
                if j < coins[i-1]:          # 容量有限，无法选择第i个硬币
                    dp2[j] = dp[j]
                else:                       # 可选择第i个硬币
                    dp2[j] = min( dp[j], dp2[j-coins[i-1]] + 1 )
            dp = dp2

        ans = dp[amount] 
        return ans if ans != amount+1 else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        dp = [amount+1] * (amount+1)    # 初始化为一个较大的值，如 +inf 或 amount+1
        dp[0] = 0        # 合法的初始化
        
        # 完全背包：优化后的状态转移
        for coin in coins:                  # 第一层循环：遍历硬币
            dp2 = [amount+1] * (amount+1)   # 滚动数组
            dp2[0] = 0
            for j in range(amount+1):       # 第二层循环：遍历背包
                if j < coin:                # 容量有限，无法选择第i个硬币
                    dp2[j] = dp[j]
                else:                       # 可选择第i个硬币
                    dp2[j] = min( dp[j], dp2[j-coin] + 1 )
            dp = dp2

        ans = dp[amount] 
        return ans if ans != amount+1 else -1

4.【一维DP，两层循环】 内层循环正序，省去滚动数组：

在状态转移过程中，每一行的 dpdp 状态值都只与其正上方和左方的状态值有关，因此可对状态空间 dpdp 进一步优化而省去滚动数组 dp2dp2：

dp[j]=min⁡{ dp[j],dp[j−wi]+1 },0<=wi<=j\textcolor{red}{dp}[j] = \min \{ \ dp[j],\quad \textcolor{red}{dp}[j-w_i] + 1\ \} ,\quad 0<=w_i<=j \quad \quad

考虑到我我们在更新 dp[j]dp[j] 时，使用的其实是上一行的 dp[j]dp[j] 和 本行已更新过的 dp[j−wi]dp[j-w_i] 的值；因此在第二层循环中，通过从小到大正序计算即可保证在计算 dp[j]dp[j] 时所用到的 dp[j]dp[j] 来自上一行，而 dp[j−wi]dp[j-w_i] 则来自本行。

⚠️ 「完全背包问题」内层循环正序，而「0-1 背包问题」中内层循环反序，从原始的状态转移方程来看，在这一点上两者的区别也是显而易见的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        dp = [amount+1] * (amount+1)    # 初始化为一个较大的值，如 +inf 或 amount+1
        dp[0] = 0        # 合法的初始化
        
        # 完全背包：优化后的状态转移
        for coin in coins:                      # 第一层循环：遍历硬币
            for j in range(coin, amount+1):     # 第二层循环：遍历背包【正序】
                dp[j] = min( dp[j], dp[j-coin] + 1 )

        ans = dp[amount] 
        return ans if ans != amount+1 else -1

复杂度分析
最终优化后：

  • 时间复杂度：O(n×amount)O(n×amount)，其中 nn 是coins数组的长度，amountamount 为总金额。

  • 空间复杂度：O(amount)O(amount)。

References:

https://leetcode-cn.com/problems/coin-change/solution/by-flix-su7s/#%E5%89%8D%E8%A8%80