一文用分治 DFS 详解01背包

· · 算法·理论

如何用分治法和 DFS 理解 01背包

Part 0 引入

01 背包是什么？

有 N 件物品和一个容量为 M 的背包。第 i 件物品的重量是 W_i，价值是 D_i。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

是的这就是 01 背包。每个物品只有“取”和“不取”两种状态。

Part 1 分治

好的那么话说回来，如果你没学背包，怎么解决？

很显然，最直接的做法是贪心（贪单位价值）。但是实际一去做会发现完全错误（你可能对样例就是了）。

那么怎么做？分治。最后一个物品只有“选”与“不选”的状态。

如果选：问题变为“在前面 N-1 个物品中，用容量为 M-W_N 的背包最多能装下多少物品？把这个得数加上 W_N。”

如果不选：问题变为“在前面 N-1 个物品中，用容量为 M 的背包最多能装下多少物品？”

如果文中是“前面 0 个物品”：简单，装得下就装，装不下跑路。

Part 1 Ex 《老人与金子》

这里是原文，十分感谢。 By SDJL

话说回来，在遥远的 CYX 国，有这样一个人：他叫 CYX，十分贪心，无恶不作。

CYX 国实力强到爆炸，以至于他有 M 个 bot 没地方用。

一天，CYX 在一举拿下了我的世界里挖一半的 N 个钻石矿坑后，他想用他的 bot 拿下所有的钻石，可他深知他无法做到。

他已经提前派人问好了每个矿坑所需要的人力 W_i 和能给他带来的价值 C_i。

然后他就心生一计：

“啊我的小AtC，如果我给你前 N-1 个矿坑和 M-W_N 个 bot，你能告诉我你能拿走多少矿石吗？”

“啊我的小CF，如果我给你前 N-1 个矿坑和 M 个 bot，你能告诉我你能拿走多少矿石吗？”

然后他心想：两位小兵都是我最信赖的人，所以我只需要把 AtC 的得数加上 C_N 以后去和 CF 的得数取个最大值就成。我真聪明嘻嘻！

然后 AtC 和 CF 也如法炮制，搞了一大堆人去问。最后到了矿场 1 那：

“所以呢？你咋不自己算一下？这玩意这么明显，能挖就挖，不能挖就没收获，我们凭啥当免费劳动力啊？”

然后所有的人都报上了自己的得数，CYX 也终于知道他能拿多少钻石了。

Part 2 优化

不难发现，里面有很多玩意重复算了，考虑开个数组记忆化。

时间复杂度一下子降了很多。