动态0/1背包问题是个笑话吗？

Question

我已经得到了一项证据，可以证明关于0/1背包问题的一个普遍看法是错误的。我真的很难相信自己是对的，因为我找不到任何地方支持我的说法。因此，我将首先陈述我的说法，然后证明它们，我希望任何人都能进一步证实或证伪我的说法。感谢任何合作。

说法：

1. 解决背包问题的bnb（分支定界）算法的规模不会与K（背包容量）无关。
2. bnb树的完整空间大小始终为O（NK），其中N为物品数量，而不是O（2^N）。
3. bnb算法在时间和空间上始终优于 标准 动态规划方法。

前提假设：bnb算法易于产生无效节点（如果剩余容量小于当前物品的重量，则不会扩展它）。此外，bnb算法是以深度优先的方式完成的。

简略证明：

下面是求解背包问题的递归公式：

Value(i,k) = max (Value(i-1,k) , Value(n-1 , k-weight(i)) + value(i)

但是，如果k < weight（i），则Value(i，k) = Value(i-1，k)

现在想象这个例子：

K = 9
N = 3   
V W:   
5 4   
6 5   
3 2

现在这里是此问题的动态解决方案和表格：

现在假设不论好坏，我们想要仅使用递归公式通过记忆化来解决这个问题，而不使用表格，通过诸如映射/字典或简单数组之类的东西来存储已访问的单元格。为了使用记忆化解决此问题，我们应该解决表示的单元格:

现在这恰好像是我们使用bnb方法获得的树形结构：

现在考虑证明:

1. 记忆化和bnb树具有相同数量的节点
2. 记忆化节点取决于表格大小
3. 表格大小取决于N和K
4. 因此 bnb不独立于K
5. 记忆化空间受NK限制，即O（NK）
6. 因此 bnb树完整空间（或如果我们按广度优先的方式执行bnb，则空间是O（NK），而不是O（N ^ 2），因为不会构造整个树，它将与记忆化完全相同。
7. 记忆化比标准动态规划更省空间。
8. bnb比动态规划更节省空间（即使以广度优先的方式进行）
9. 简单的bnb（仅消除不可行节点）的时间比记忆化好。
10. 如果不考虑记忆查找，那么它比动态规划好。
11. 因此bnb算法在时间和空间上总是优于动态规划。

问题:

如果我的证明正确，那么会出现一些有趣的问题：

1. 为什么要使用动态规划？在我看来，在dp背包中最好的方法就是只保留最后两列，并且如果您从下到上填充它，可以进一步改进为一列，但是（如果上述断言正确）仍然无法击败bnb方法，尽管它使用O（K）空间。
2. 如果我们将relaxation pruning集成到bnb中，我们仍然可以说bnb更好（与时间有关吗）？

附言:很抱歉文章太长了！

编辑：

由于两个答案都集中在记忆化上，我想澄清一下，我根本没有关注这个！我只是使用记忆化作为一种技术来证明我的断言。我的主要重点是分支限界技术与动态规划的比较，以下是另一个问题的完整示例，通过bnb +松弛解决（来源：Coursera - 离散优化）：

- Amen

---

更适合于https://cs.stackexchange.com/。 - Eugene Sh.

我建议关闭这个问题，因为它更适合于https://cs.stackexchange.com/。请注意不要改变原意，尽可能让翻译通俗易懂。 - Jim Mischel

我该如何将它移动到那里？ - Amen

你可能想避免使用像“完全的笑话”这样的短语，因为它会引起人们的警觉。 - m69 ''snarky and unwelcoming''

总结一下，我在解决修改后的找零问题和随后的调查中发现，标准的（“经典”的）DP解法远不如一个不错的BnB解法，该解法还使用了受限制的记忆化缓存。我甚至没有找到任何测试案例，其中BnB + 记忆化解法的速度远慢于经典DP解法，这让我对为什么经典DP解法更常用感到困惑。 - RBarryYoung

Answer 1

首先，由于你正在应用记忆化技术，因此你仍在进行DP。这基本上是DP的定义：递归+记忆化。而且这也很好。如果没有记忆化，你的计算成本将会爆炸。想象一下，如果两个物品都重量为2，第三个和第四个重量为1。它们最终都到达树中的同一个节点，你就必须多次计算并且最终会得到指数时间复杂度。

主要区别在于计算的顺序。计算整个矩阵的方法称为“自底向上DP”，因为你从(0,0)开始向上工作。你的方法（树形方法）称为“自顶向下DP”，因为你从目标开始向下工作。但它们都是使用动态规划。

现在回答你的问题：

你高估了你真正节省的量。N = 3是一个相当小的例子。我尝试了一个更大的例子，N=20, K=63（仍然相当小），以及随机的值和随机的权重。这是我生成的第一张图片：

values: [4, 10, 9, 1, 1, 2, 1, 2, 6, 4, 8, 9, 8, 2, 8, 8, 4, 10, 2, 6]
weights: [6, 4, 1, 10, 1, 2, 9, 9, 1, 6, 2, 3, 10, 7, 2, 4, 10, 9, 8, 2]
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111
011111111111111111111111111111111111111111111111111111111111101
000001011111111111111111111111111111111111111111111111111111101
000000010111111111111111111111111111111111111111111111111111101
000000000010101011111111111111111111111111111111111111111010101
000000000000000000001010101111111111111111111111111111111010101
000000000000000000000000000101010101111111111111111111101010101
000000000000000000000000000001010101011111111111111111101010101
000000000000000000000000000000000101000001111100001111100000101
000000000000000000000000000000000000000000010100000111100000101
000000000000000000000000000000000000000000000000000010100000101
000000000000000000000000000000000000000000000000000000000000101
000000000000000000000000000000000000000000000000000000000000001

这个图片是你展示的矩阵的转置版本。行代表值(在数组中的前i个元素)，列代表允许的权重k值。1表示DP矩阵中您将访问的位置。当然，在矩阵底部你会看到很多0，但是你将访问位于上半部分的每个位置。矩阵中大约68%的位置被访问到。在这种情况下，自底向上的DP解决方案将更快。递归调用较慢，因为您必须为每个递归调用分配一个新的堆栈帧。使用循环而不是递归调用加速2倍是很常见的，这已经足以使底部向上的方法更快了。我们还没有谈论树方法的记忆成本。

请注意，我这里没有使用实际的bnb。我不太确定如何处理界限，因为只有在访问其子节点计算后，您才知道节点的值。

使用我的输入数据，自底向上的方法显然是胜利者。但这并不意味着你的方法不好。相反，它可能非常好。这完全取决于输入数据。假设K=10^18，所有的权重都约为10^16。自底向上的方法甚至找不到足够的内存来分配矩阵，而你的方法将在很短的时间内成功。

然而，您可能可以通过执行A*而不是bnb来改进您的版本。您可以使用int(k / max(weight[1..i]) * min(values[1..i])估计每个节点值的最佳值，并使用该启发式方法修剪许多节点。

- Jakube

Answer 2

我认为你误解了动态规划是背包问题的最先进解决方案。这个算法在大学里教授，因为它是动态规划和伪多项式时间算法的一个简单而好的例子。

我对这个领域没有专业知识，不知道现在的最新技术是什么，但分支定界方法已经被用了相当长一段时间来解决背包问题：书籍Knapsak-Problems by Martello and Toth已经相当老了，但非常详细地介绍了分支定界。

尽管如此，你的观察是很好的，分支定界方法可以用于背包问题——可惜你出生得太晚，无法成为第一个想到这个想法的人 :)

在你的证明中有一些我不理解的地方，我认为需要更多的解释。

1. 你需要记忆化，否则你的树将会有 O(2^N) 个节点（否则背包问题不会是 NP-hard）。我在你的证明中没有看到任何东西，证明记忆化的内存/计算步骤小于 O(NK)。
2. 动态规划只需要 O(K) 的内存空间，所以我不明白为什么你会声称 "bnb 算法在时间和空间上都比动态规划好"。

也许你的说法是正确的，但我无法从当前的证明中看出来。

另一个问题是 "更好" 的定义。如果分枝限界法对大多数问题或常见问题更好，那它是否更好，还是必须在最坏情况下更好（这在实际生活中没有任何作用）？

我链接的书中还有一些算法的运行时间比较。基于动态规划的算法（显然比学校教的那种复杂得多）对某些问题甚至更好 - 见第 2.10.1 节。对于一个完全的笑话来说，这并不差！

- ead

Answer 3

实际上，动态规划在整数0/1背包问题中更好，因为：

1. 没有递归，这意味着您永远不会遇到堆栈溢出
2. 无需为每个节点进行查找搜索，因此通常更快
3. 正如您所指出的，存储最后两列意味着内存要求更低
4. 代码更简单（不需要记忆化表）

- Peter de Rivaz

---

我的主要关注点是bnb vs dynamic。记忆化被提到来证明我的观点。 - Amen

没有记忆化，bnb可能会慢得多，因为它会重新访问节点，并且在最坏情况下可能是2^n复杂度。我建议您尝试比较一些实际示例的实际执行时间：个人而言，我更喜欢编写记忆化递归算法，但通常需要转换为动态规划以获得足够的速度。 - Peter de Rivaz

不要混淆记忆化和分支定界，它们是完全不同的。分支定界是一棵树！在树中，每个节点只有一个入边，因此不存在重新计算的情况！ - Amen