【背包问题の第一讲】那就从 0-1 背包问题开始讲起吧

前言

今天是我们讲解动态规划专题中的 「背包问题」的第一天。

在这个愉快的周五，我们正式吹起「DP 背包问题」的号角 🎉 🎉 ~

前不久我们刚结束「动态规划专题」的首个系列：路径问题。

如果你还没看过，我十分建议你抽时间去学习一下。因为 路径问题 里教到的「经验解法」和「技巧解法」将会贯穿我们之后的所有「动态规划专题」系列。

老规矩，我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解（每 2~3 天更新一篇，确保大家消化）。

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~

背包问题本质

背包问题是「动态规划」中十分经典的一类问题，背包问题本质上属于组合优化的「NPNPNP 完全问题」。

如果你不了解什么是「NPNPNP 完全问题」，没有关系，丝毫不影响你求解背包问题。

你可以将「NPNPNP 完全问题」简单理解为「无法直接求解」的问题。

例如「分解质因数」问题，我们无法像四则运算（加减乘除）那样，按照特定的逻辑进行求解。

只能通过「穷举」+「验证」的方式进行求解。

既然本质上是一个无法避免「穷举」的问题，自然会联想到「动态规划」，事实上背包问题也同时满足「无后效性」的要求。

这就是为什么「背包问题」会使用「动态规划」来求解的根本原因。

如果按照常见的「背包问题」的题型来抽象模型的话，「背包问题」大概是对应这样的一类问题：

泛指一类「给定价值与成本」，同时「限定决策规则」，在这样的条件下，如何实现价值最大化的问题。

今天我们要讲的是「背包问题」中的 01背包问题。

「01背包」是指给定物品价值与体积（对应了「给定价值与成本」），在规定容量下（对应了「限定决策规则」）如何使得所选物品的总价值最大。

题目描述

有 NNN 件物品和一个容量是 VVV 的背包。每件物品有且只有一件。

第 iii 件物品的体积是 v[i]v[i]v[i]，价值是 w[i]w[i]w[i]。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

示例 1：

输入: N = 3, C = 4, v = [4,2,3], w = [4,2,3]
输出: 4
解释: 只选第一件物品，可使价值最大。
复制代码

示例 2：

输入: N = 3, C = 5, v = [4,2,3], w = [4,2,3]
输出: 5
解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。
复制代码

dp[N][C+1]  解法

即使我们从没接触过背包问题，也能使用在 路径问题 中学到的「技巧解法」来分析。

如果要我们设计一个 DFS 函数对所有的方案进行枚举的话，大概是这么一个函数签名：

int dfs (int[] v, int[] w, int i, int c);
复制代码

其中 vvv 和 www 对应了输入的「物品体积」和「物品价值」，属于不变参数，无须考虑。

而 iii 和 ccc 分别代表「当前枚举到哪件物品」和「现在的剩余容量」。

返回值则是我们问题的答案：最大价值。

那么根据变化参数和返回值，可以抽象出我们的 dp 数组：

一个二维数组，其中一维代表当前「当前枚举到哪件物品」，另外一维「现在的剩余容量」，数组装的是「最大价值」。

根据 dp 数组不难得出状态定义：

考虑前 iii 件物品，使用容量不超过 CCC 的条件下的背包最大价值。

当有了状态定义之后，我们再根据「最后一步」选择来推导「状态转移方程」。

不失一般性的，我们只需要考虑第 iii 件物品如何选择即可，对于第 iii 件物品，我们有「选」和「不选」两种决策。

结合我们的「状态定义」，「不选」方案的「最大价值」很好确定：

「不选」其实就是 dp[i−1][c]dp[i - 1][c]dp[i−1][c]，等效于我们只考虑前 i−1i - 1i−1 件物品，当前容量为 ccc 的情况下的最大价值。

同理，如果我们选第 iii 件物品的话，代表消耗了 v[i]v[i]v[i] 的背包容量，获取了 w[i]w[i]w[i] 的价值，那么留给前 i−1i - 1i−1 件物品的背包容量就只剩 c−v[i]c - v[i]c−v[i]。即最大价值为 dp[i−1][c−v[i]]+w[i]dp[i - 1][c - v[i]] + w[i]dp[i−1][c−v[i]]+w[i]。

当然，选第 iii 件有一个前提：「当前剩余的背包容量」⩾\geqslant⩾「物品的体积」。

在「选」和「不选」之间取最大值，就是我们「考虑前 iii 件物品，使用容量不超过 CCC 」的条件下的「背包最大价值」。

即可得「状态转移方程」为：

代码：

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[N][C+1];
        // 先处理「考虑第一件物品」的情况
        for (int i = 0; i <= C; i++) {
            dp[0][i] = i >= v[0] ? w[0] : 0;
        }
        // 再处理「考虑其余物品」的情况
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < C + 1; j++) {
                // 不选该物品
                int n = dp[i-1][j]; 
                // 选择该物品，前提「剩余容量」大于等于「物品体积」
                int y = j >= v[i] ? dp[i-1][j-v[i]] + w[i] : 0; 
                dp[i][j] = Math.max(n, y);
            }
        }
        return dp[N-1][C];
    }
}
复制代码

• 时间复杂度：共有 N∗CN * CN∗C 个状态需要被转移，复杂度为 O(N∗C)O(N * C)O(N∗C)
• 空间复杂度：O(N∗C)O(N * C)O(N∗C)

dp[2][C+1] 解法

根据「转移方程」，我们知道计算第 iii 行格子只需要第 i−1i - 1i−1 行中的某些值。

也就是计算「某一行」的时候只需要依赖「前一行」。

因此可以用一个只有两行的数组来存储中间结果，根据当前计算的行号是偶数还是奇数来交替使用第 0 行和第 1 行。

这样的空间优化方法称为「滚动数组」，我在 路径问题 第四讲 也曾与你分享过。

这种空间优化方法十分推荐，因为改动起来没有任何思维难度。

只需要将代表行的维度修改成 2，并将所有使用行维度的地方从 iii 改成 i%2i\%2i%2 或者 i&1i\&1i&1 即可（更建议使用 i&1i\&1i&1，& 运算在不同 CPU 架构的机器上要比 % 运算稳定）。

代码：

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[][] dp = new int[2][C+1];
        // 先处理「考虑第一件物品」的情况
        for (int i = 0; i < C + 1; i++) {
            dp[0][i] = i >= v[0] ? w[0] : 0;
        }
        // 再处理「考虑其余物品」的情况
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < C + 1; j++) {
                // 不选该物品
                int n = dp[(i-1)&1][j]; 
                // 选择该物品
                int y = j >= v[i] ? dp[(i-1)&1][j-v[i]] + w[i] : 0;
                dp[i&1][j] = Math.max(n, y);
            }
        }
        return dp[(N-1)&1][C];
    }
}
复制代码

• 时间复杂度：共有 N∗CN * CN∗C 个状态需要被转移，复杂度为 O(N∗C)O(N * C)O(N∗C)
• 空间复杂度：O(C)O(C)O(C)

dp[C+1] 解法

事实上，我们还能继续进行空间优化，只保留代表「剩余容量」的维度。

再次观察我们的「转移方程」：

不难发现当求解第 iii 行格子的值时，不仅是只依赖第 i−1i - 1i−1 行，还明确只依赖第 i−1i - 1i−1 行的第 ccc 个格子和第 c−v[i]c - v[i]c−v[i] 个格子（也就是对应着第 iii 个物品不选和选的两种情况）。

换句话说，只依赖于「上一个格子的位置」以及「上一个格子的左边位置」。

因此，只要我们将求解第 iii 行格子的顺序「从 000 到 ccc 」改为「从 ccc 到 000」，就可以将原本 2 行的二维数组压缩到一行（转换为一维数组）。

这样做的空间复杂度和「滚动数组」优化的空间复杂度是一样的。但仍然具有意义，而且这样的「一维空间」优化，是求解其他背包问题的基础，需要重点掌握。

代码：

class Solution {
    public int maxValue(int N, int C, int[] v, int[] w) {
        int[] dp = new int[C + 1];
        for (int i = 0; i < N; i++) {
            for (int j = C; j >= v[i]; j--) {
                // 不选该物品
                int n = dp[j]; 
                // 选择该物品
                int y = dp[j-v[i]] + w[i]; 
                dp[j] = Math.max(n, y);
            }
        }
        return dp[C];
    }
}
复制代码

• 时间复杂度：共有 N∗CN * CN∗C 个状态需要被转移，复杂度为 O(N∗C)O(N * C)O(N∗C)
• 空间复杂度：O(C)O(C)O(C)

总结

今天，三叶向你讲解了什么是背包问题、背包问题的本质是什么以及为什么背包问题需要用到动态规划来求解 ...

其中「01背包」问题是众多背包问题中核心。

我们从 01背包 的「常规解法」优化到「滚动数组解法」，再优化到「一维空间优化解法」。

理解「一维空间优化解法」十分重要，这是我们之后学习其他背包问题的基础。

其他背包问题一定程度上都能转化成「01背包」来进行求解，或是根据「01背包」的转移方程来稍作修改进行求解。

背包问题（目录）

1. 01背包 : 本篇

1. 【练习】01背包 : 背包问题 第二讲
   
2. 【学习&练习】01背包 : 背包问题 第三讲
   

2. 完全背包 : 背包问题 第四讲

1. 【练习】完全背包 : 背包问题 第五讲
   
2. 【练习】完全背包 : 背包问题 第六讲
   
3. 【练习】完全背包 : 背包问题 第七讲
   

3. 多重背包 : 背包问题 第八讲
   
4. 多重背包（优化篇）

1. 【上】多重背包（优化篇）: 背包问题 第九讲
   
2. 【下】多重背包（优化篇）: 背包问题 第十讲
   

5. 混合背包 : 背包问题 第十一讲
   
6. 分组背包 : 背包问题 第十二讲

1. 【练习】分组背包 : 背包问题 第十三讲

7. 多维背包

1. 【练习】多维背包 : 背包问题 第十四讲
   
2. 【练习】多维背包 : 背包问题 第十五讲
   

8. 树形背包 : 背包问题 第十六讲

1. 【练习篇】树形背包
   
2. 【练习篇】树形背包
   

9. 背包求方案数

1. 【练习】背包求方案数

10. 背包求具体方案

1. 【练习】背包求具体方案

11. 泛化背包

1. 【练习】泛化背包