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

Question

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

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

我在克莱因伯格的书中读到了背包问题。根据我的理解，动态规划是将问题分解成重叠的子问题——然而，我在各种书籍/在线资源中看到过此表用于解决背包问题。我似乎不知道这个表是如何与动态规划联系在一起的？我们在这张桌子上记东西吗？在我看来，这似乎是一个巧妙的解决方案的背包，但不是一个动态规划之一。我看过视频和文本，其中他们通过使用表格或使用动态编程解决方案来解决问题，但似乎没有人提供两者之间的联系。

Answer 1

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

您的输入由n不同的项组成，数字W；W是显式的，而不是通过输入的大小来暗示。因为我们正在使用一些有效的编码（即二进制）来提供W，所以W的大小在W的编码中是指数级的。也就是说，输入包含代表W的O（lgW）位，但是我们构建的表有W行（或列，根据您的查看方式加深）。这使得算法在输入大小上呈指数级。

然而，如果我们放松了必须有效表示输入的常规规则，我们可以使用“一元”符号指定W<代码>W输入中的1s，而不是二进制表示。现在您可以声明，由于输入大小在n和W中是多项式，而不是像以前那样在n和lg W中，因此DP表在输入中也是多项式的。

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