algorithm - 背包问题中的表与动态规划之间有什么联系？

Question

对于一个非常新手的问题，我深表歉意，因为我无法从各种资源中找到答案。

在背包算法中，我们构造一个表，例如在 https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

我在 Kleinberg 的书中读到了背包问题。根据我的理解，动态规划是将问题分解为重叠的子问题——但是，我在各种书籍/在线资源中看到这张表用于解决背包问题。我似乎无法理解这张表如何链接到动态规划？我们是否正在记住这张表中的任何内容？在我看来，这似乎是背包问题的巧妙解决方案，但不是动态规划解决方案。我看过视频和文本，他们通过使用表格或使用动态规划解决方案来解决问题，但似乎没有人提供两者之间的联系。

Answer 1

还是动态规划。唯一的区别是动态规划算法在n 中仍然不是多项式的。 , 但在两个n和 W .对于这些类型的问题，您必须区分因输入而自然产生的值和作为输入的一部分的值。

您的输入包括 n不同的元素和数量W ; W是明确的，而不是由输入的大小暗示的。因为我们正在使用一些有效的编码(即二进制)来提供 W , 大小为 W在 W 的编码中是指数 .也就是说，输入包含 O(lg W ) 位表示 W , 但我们建立的表有 W行(或列，深入了解您的看法)。这使得算法的输入大小呈指数增长。

但是，如果我们放宽输入必须有效表示的通常规则，我们可以指定 W使用“一元”符号； W输入中的 1s 而不是二进制表示。现在你可以声明了，因为输入大小是 n 中的多项式和 W , 而不是 n和 lg W和以前一样，DP 表在输入中也是多项式的。

这大致是强 NP 难和弱 NP 难的区别:如果一个问题是弱 NP 难的，那么如果我们指定一些数值的一元编码，就可以找到多项式时间算法(通常基于动态规划)参数而不是通常的二进制编码。