0-1 背包

非常经典 a, 感觉从小说到大 —— 先说模板题

有 n 个物品，第 i 个物品：

• 重量为 weight[i]
• 价值为 value[i] 有一个容量为 W 的背包。

每个物品只能：

• 不选：0
• 选一次：1 问在总重量不超过 W 的情况下，最多能获得多少价值？

实际上我们要看的就是对于一个序列, 各个元素只有两个状态 —— 选 / 不选. 那么显然可以回溯 dfs 暴力解决. 假设 dfs(i, c) 表示在 [0, i) 的物品, 剩余 c 容量的情况下, 我们能取到的最大值.

dfs(i, remainingCapacity):
	拿 -> 转移下一个状态  (如果装的下)
	不拿 -> 转移下一个状态
	取最大值

那么我们重新反思这个深搜 —— 对于某个 dfs(i, c) 来说, 我们存在重复搜索的情况 —— 对于同一个 i, c 有可能会通过不同的路径走到. 所以记忆化一下, 解决了

实际上我们发现可以使用记忆化来进行优化, 不过稍微再深入思考一下 —— 我们定义 dfs 的时候, 实际上需要记录两个状态 —— 一个是现在有多少物品在我们的选购清单里(i), 另一个是我们现在还剩多少容量(remainingCapacity)

也就是为了知道最优答案, 我们至少需要知道两个信息. 所以为了表达整个搜索空间, 我们可以使用 dp[i][j] 这样的一个二维空间来进行表示 —— 在允许选取前 i 个物品, 剩余容量为 j 的时候的最优解是什么.

继续填表, 对于 dp[i][j] 来说, 假设前面都填好了, 我们现在只需要考虑两件事情 —— i 选还是不选?

对于不选来说, 非常简单, 继承一下上一次结果即可 dp[i][j] = dp[i - 1][j], 我们没有增加新的价值, 最大容量也没有什么变化.

对于选来说, 略微复杂一些, 首先 j 要大于 weight[i], 说明现在可以进行选取, 然后此时的状态就转移成 "在容量 j - weight[i] 的时候(因为要空出来给当前物品存放的空间), 我们拥有 i - 1 的物品可以选的时候的最优解是什么" —— dp[i][j] = dp[i - 1][j - weight[i]] + value 于是状态转移方程就写好了

dp[i][j] = std::max(
	dp[i - 1][j],
	dp[i - 1][j - weight[i]] + value[i]
)

其他

由于 0-1 拥有很不错的性质 —— 我们的状态就是二元的, 选 / 不选. 也就是说它实际上天然的把我们的数据划分成了两组, 一组是存入背包中的, 一组是不在背包内的.

那么对于一些划分数组的题目, 也可以想到 0-1 背包.

综上所述, 感觉

• 背包 —— 一个确定序列
• 0-1 —— 一个确定的二元状态

那么实际上看到这样的条件, 不妨想想 0-1 背包问题.