algorithm - 动态0/1背包总是一个玩笑吗？

我已经获得了证明，该证据会使关于0/1背包问题的普遍想法蒙羞，我真的很难说服我自己是对的，因为我找不到可以支持我的主张的任何东西，因此我将首先陈述我的主张，然后证明它们，我希望任何人尝试进一步证实我的主张或取消其主张。任何合作表示赞赏。
断言:

用于解决背包问题的bnb(分支和边界)算法的大小是，而不是，与K(背包的容量)无关。

bnb树完整空间的大小始终为O(NK)的，始终为，其中N为项数，而不是 O(2 ^ N)

在时间和空间上，bnb算法总是优于标准动态编程方法。

前提条件:bnb算法容易产生无效节点(如果剩余容量小于当前项目的权重，我们将不对其进行扩展。此外，bnb算法以深度优先的方式进行。
草率证明:
这是解决背包问题的递归公式:
值(i，k)=最大值(值(i-1，k)，值(n-1，k权重(i))+值(i)
但是如果k 现在想象一下这个例子:

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

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

现在想象一下，不管这是否是一个好主意，我们都只想通过内存来使用递归公式，而不要通过表格来实现此目的，而要使用诸如 map /字典或简单数组的形式来存储访问的单元格。为了使用内存来解决此问题，我们应该解决表示的单元格:

现在，这就像我们使用bnb方法获得的树:

，现在用于草率的证明:

记忆化和bnb树具有相同数量的节点

内存节点取决于表大小

表大小取决于N和K

因此 bnb并不独立于K

内存空间受NK限制，即O(NK)

因此， bnb树的完整空间(或如果我们以广度优先的方式进行bnb的空间)始终为O(NK)而不是O(N ^ 2)，因为整棵树都不会被构建并且就像妈妈一样。

记忆化比标准动态编程具有更好的空间。

bnb的空间比动态编程要好(即使先广度执行)

简单的bnb无需放松(并且仅消除不可行的节点)将比内存有更好的时间(内存必须在查找表中进行搜索，即使查找可以忽略，它们仍然是相同的。)

如果我们忽略备忘录的查找搜索，则它比动态搜索要好。

因此， bnb算法在时间和空间上总是比动态更好。

问题:
如果无论如何我的证明是正确的，将会出现一些有趣的问题:

为什么要打扰动态编程？以我的经验，您可以在dp背包中做的最好的事情是拥有最后两列，如果从下至上填充它，您可以将其进一步改进为一列，并且它具有O(K)的空间，但仍然不能(如果以上说法正确)击败了bnb方法。

如果我们将bnb与放松修剪(就时间而言)整合在一起，我们还能说bnb更好吗？

ps:很抱歉，很长很长时间!
编辑:
由于其中两个答案都集中在内存上，因此我只想澄清一下，我并没有完全专注于这个!我只是将内存作为一种证明我的主张的技术。我的主要重点是分支定界技术与动态编程，这是另一个问题的完整示例，通过bnb +松弛解决(来源:Coursera-离散优化):

最佳答案

我认为从您的角度出发存在一个误解，那就是动态编程是背包问题的最新解决方案。该算法是在大学中教授的，因为它是动态编程和伪多项式时间算法的简单而出色的示例。

我没有该领域的专业知识，也不知道现在有什么最新技术，但是分支定界方法已经使用了相当长的时间来解决背包问题:Knapsak-Problems by Martello and Toth这本书已经很漂亮了较旧，但对分支绑定(bind)的处理相当广泛。

不过，从您的角度来看，这仍然是一个很好的观察，分支和绑定(bind)方法可以用于背包-las，您出生得太晚了，所以第一个没有这个想法的人就知道了:)

您的证明中有一些我不理解的地方，在我看来还需要更多解释:

您需要内存，否则您的树将具有O(2^N)节点(显然会有这种情况，否则背包将不会具有NP难度)。我在您的证明中看不到任何东西，可以确保内存存储/计算步骤少于O(NK)。

动态编程仅需要O(K)内存空间，因此我不明白为什么您可以宣称“bnb算法在时间和空间上总是比动态更好”。

也许您的说法是正确的，但我现在无法以证明的方式来了解它。

另一个问题是“更好”的定义。如果分支定界方法对于大多数问题或常见问题更好，还是必须对最坏情况(在现实生活中没有任何作用)更好，那么它是更好的选择吗？

我链接到的这本书也对算法的运行时间进行了一些比较。基于动态编程的算法(显然比在学校教授的算法更复杂)对于某些问题甚至更好-请参见第2.10.1节。完全是个笑话!