【动态规划/背包问题】如何将原问题抽象为「01 背包」问题 ...
【动态规划/背包问题】如何将原问题抽象为「01 背包」问题 ...
前言
今天是我们讲解「动态规划专题」中的 「背包问题」的第二天。
在众多背包问题中「01 背包问题」是最为核心的，因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。
另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解（每 2~3 天更新一篇，确保大家消化）。
你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~
题目描述
这是 LeetCode 上的「416. 分割等和子集」，难度为 Medium。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
基本分析
通常「背包问题」相关的题，都是在考察我们的「建模」能力，也就是将问题转换为「背包问题」的能力。
由于本题是问我们能否将一个数组分成两个「等和」子集。
问题等效于「能否从数组中挑选若干个元素，使得元素总和等于所有元素总和的一半」。
这道题如果抽象成「背包问题」的话，应该是：
我们背包容量为
，每个数组元素的「价值」与「成本」都是其数值大小，求我们能否装满背包。
转换为 01 背包
由于每个数字（数组元素）只能被选一次，而且每个数字选择与否对应了「价值」和「成本」，求解的问题也与「最大价值」相关。
可以使用「01 背包」的模型来做。
当我们确定一个问题可以转化为「01 背包」之后，就可以直接套用「01 背包」的状态定义进行求解了。
注意，我们积累 DP 模型的意义，就是在于我们可以快速得到可靠的「状态定义」。
在 路径问题 中我教过你通用的 DP 技巧解法，但那是基于我们完全没见过那样的题型才去用的，而对于一些我们见过题型的 DP 题目，我们应该直接套用（或微调）该模型「状态定义」来做。
我们直接套用「01 背包」的状态定义：
代表考虑前
个数值，其选择数字总和不超过
的最大价值。
当有了「状态定义」之后，结合我们的「最后一步分析法」，每个数字都有「选」和「不选」两种选择。
因此不难得出状态转移方程：
代码：
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
//「等和子集」的和必然是总和的一半
int sum = 0;
for (int i : nums) sum += i;
int target = sum / 2;
// 对应了总和为奇数的情况，注定不能被分为两个「等和子集」
if (target * 2 != sum) return false;
int[][] f = new int[n][target + 1];
// 先处理考虑第 1 件物品的情况
for (int j = 0; j <= target; j++) {
f[0][j] = j >= nums[0] ? nums[0] : 0;
}
// 再处理考虑其余物品的情况
for (int i = 1; i < n; i++) {
int t = nums[i];
for (int j = 0; j <= target; j++) {
// 不选第 i 件物品
int no = f[i-1][j];
// 选第 i 件物品
int yes = j >= t ? f[i-1][j-t] + t : 0;
f[i][j] = Math.max(no, yes);
}
}
// 如果最大价值等于 target，说明可以拆分成两个「等和子集」
return f[n-1][target] == target;
}
}
- 时间复杂度：
为数组总和的一半，
数组元素个数。为共有
个状态需要被转移，复杂度为
- 空间复杂度：
「滚动数组」解法
在上一讲我们讲到过「01 背包」具有两种空间优化方式。
其中一种优化方式的编码实现十分固定，只需要固定的修改「物品维度」即可。
代码：
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
//「等和子集」的和必然是总和的一半
int sum = 0;
for (int i : nums) sum += i;
int target = sum / 2;
if (target * 2 != sum) return false;
// 将「物品维度」修改为 2
int[][] f = new int[2][target + 1];
// 先处理考虑第 1 件物品的情况
for (int j = 0; j <= target; j++) {
f[0][j] = j >= nums[0] ? nums[0] : 0;
}
// 再处理考虑其余物品的情况
for (int i = 1; i < n; i++) {
int t = nums[i];
for (int j = 0; j <= target; j++) {
// 不选第 i 件物品，将物品维度的使用加上「&1」
int no = f[(i-1)&1][j];
// 选第 i 件物品，将物品维度的使用加上「&1」
int yes = j >= t ? f[(i-1)&1][j-t] + t : 0;
f[i&1][j] = Math.max(no, yes);
}
}
// 如果最大价值等于 target，说明可以拆分成两个「等和子集」
// 将物品维度的使用加上「&1」
return f[(n-1)&1][target] == target;
}
}
- 时间复杂度：
为数组总和的一半，
数组元素个数。为共有
个状态需要被转移，复杂度为
- 空间复杂度：
「一维空间优化」解法
事实上，我们还能继续进行空间优化：只保留代表「剩余容量」的维度，同时将容量遍历方向修改为「从大到小」。
代码：
class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
//「等和子集」的和必然是总和的一半
int sum = 0;
for (int i : nums) sum += i;
int target = sum / 2;
// 对应了总和为奇数的情况，注定不能被分为两个「等和子集」
if (target * 2 != sum) return false;
// 将「物品维度」取消
int[] f = new int[target + 1];
for (int i = 0; i < n; i++) {
int t = nums[i];
// 将「容量维度」改成从大到小遍历
for (int j = target; j >= 0; j--) {
// 不选第 i 件物品
int no = f[j];
// 选第 i 件物品
int yes = j >= t ? f[j-t] + t : 0;
f[j] = Math.max(no, yes);
}
}
// 如果最大价值等于 target，说明可以拆分成两个「等和子集」
return f[target] == target;
}
}
- 时间复杂度：
为数组总和的一半，
数组元素个数。为共有
个状态需要被转移，复杂度为
- 空间复杂度：
总结
今天我们对昨天学的「01 背包」进行了应用。
可以发现，本题的难点在于「对问题的抽象」，主要考察的是如何将原问题转换为一个「01 背包」问题。
事实上，无论是 DP 还是图论，对于特定问题，大多都有相应的模型或算法。
难是难在如何将问题转化为我们的模型。
至于如何培养自己的「问题抽象能力」？
首先通常需要我们积累一定的刷题量，并对「转换问题的关键点」做总结。
例如本题，一个转换「01 背包问题」的关键点是我们需要将「划分等和子集」的问题等效于「在某个数组中选若干个数，使得其总和为某个特定值」的问题。
拓展
但这道题到这里还有一个”小问题“。
就是我们最后是通过「判断」来取得答案的。
通过判断取得的最大价值是否等于
来决定是否能划分出「等和子集」。
虽然说逻辑上完全成立，但总给我们一种「间接求解」的感觉。
造成这种「间接求解」的感觉，主要是因为我们没有对「01 背包」的「状态定义」和「初始化」做任何改动。
但事实上，我们是可以利用「01 背包」的思想进行「直接求解」的。
因此在下一讲，我们还会再做一遍这道题。
不过却是以「另外一个角度」的「01 背包」思维来解决。
敬请期待 ~
背包问题（目录）
- 01背包 : 背包问题 第一讲
- 【练习】01背包 : 本篇
- 【学习&练习】01背包
- 完全背包
- 【练习】完全背包
- 多重背包
- 【练习】多重背包
- 多重背包（优化篇）
- 【练习】多重背包（优化篇）
- 【练习】多重背包（优化篇）
- 混合背包
- 【练习】混合背包
- 分组背包
- 【练习】分组背包
- 多维背包
- 【练习】多维背包
- 树形背包
- 【练习篇】树形背包
- 背包求方案数
- 【练习】背包求方案数
- 背包求具体方案
- 【练习】背包求具体方案
- 泛化背包
- 【练习】泛化背包
最后
这是我们「刷穿 LeetCode」系列文章的第 No.416 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。