我知道这Knapsack是 NP 完全的，而 DP 可以解决它。他们说 DP 解决方案是pseudo-polynomial，因为它是“输入长度”的指数（即编码输入所需的位数）。不幸的是我没有得到它。谁能pseudo-polynomial慢慢给我解释一下？
问问题
40212 次
5 回答
107
对于具有 N 个物品和大小为 W 的背包的无界背包问题，运行时间为 O(NW)。不过，W 在输入长度上不是多项式，这就是使其成为伪多项式的原因。
考虑 W = 1,000,000,000,000。表示这个数字只需要 40 位，因此输入大小 = 40，但计算运行时使用因子 1,000,000,000,000，即 O(2 40 )。
因此，运行时间更准确地说是 O( W 中的 N.2 位)，它是指数的。
另见：
于 2010-12-27T12:35:54.690 回答
34
在我们的大多数问题中，我们都在处理大量适合标准 int/float 数据类型的数字列表。由于大多数处理器的构建方式是一次处理 4-8 个字节的数字而无需额外的成本（相对于不适合的数字，比如 1 个字节），我们很少会遇到因扩大数字而导致运行时间的变化或在我们在实际问题中遇到的范围内 - 所以主导因素仍然只是数据点的绝对数量，我们习惯的 n 或 m 因素。
（您可以想象，Big-O 表示法隐藏了一个常数因子，该因子将每个数据划分出 32 或 64 位，只要我们的每个数字适合那么多位或更少，就只留下数据点的数量)
但是尝试使用其他算法重新处理涉及大整数的数据集 - 需要超过 8 个字节来表示的数字 - 并查看它对运行时的影响。所涉及的数字的大小总是会产生影响，即使在其他算法（如二进制排序）中，一旦您扩展超出安全缓冲区的缓冲区，传统处理器通过处理 4-8 字节批处理给我们“免费”。
我们讨论的背包算法的诀窍是它对特定参数 W 的大小异常敏感（相对于其他算法）。将一位添加到 W 并且算法的运行时间加倍。在此之前，我们还没有看到其他算法对价值变化的那种戏剧性反应，这就是为什么我们似乎在以不同的方式对待背包 - 但这是对它如何以非多项式方式响应的真实分析输入大小的变化。
于 2013-10-16T06:11:10.093 回答
16
我理解这一点的方式是，如果容量输入是 [1,2,...,W] 的数组，其大小为 W，则容量将为 O(W)。但容量输入不是一个数字数组，而是一个整数。时间复杂度与输入大小的关系有关。整数的大小不是整数的值，而是表示它的位数。我们稍后在算法中将这个整数 W 转换为数组 [1,2,...,W] ，导致人们误以为 W 是大小，但这个数组不是输入，整数本身是。
将输入视为“一组东西”，将大小视为“数组中有多少东西”。项目输入实际上是数组中 n 个项目的数组，因此 size=n。容量输入不是其中的 W 数字数组，而是单个整数，由 log(W) 位数组表示。将它的大小增加 1（添加 1 个有意义的位），W 加倍，因此运行时间加倍，因此指数时间复杂度。
于 2018-01-22T19:38:05.123 回答
10
背包算法的运行时间不仅受限于输入的大小（n - 物品的数量），还受限于输入的大小（W - 背包容量）O(nW)，它是指数级的在计算机中以二进制 (2^n) 表示。计算复杂性（即如何通过位在计算机内部进行处理）仅与输入的大小有关，而不与它们的大小/值有关。
暂时忽略价值/重量列表。假设我们有一个背包容量为 2 的实例。W 将在输入数据中占用两位。现在我们将背包容量增加到 4，保留其余的输入。我们的输入只增加了一位，但计算复杂度增加了两倍。如果我们将容量增加到 1024，我们将只有 10 位 W 的输入而不是 2，但复杂度增加了 512 倍。时间复杂度以二进制（或十进制）表示的 W 大小呈指数增长.
另一个帮助我理解伪多项式概念的简单例子是朴素素数测试算法。对于给定的数字 n，我们正在检查它是否被 2..√n 范围内的每个整数均分，因此该算法需要 √(n−1) 个步骤。但在这里，n 是输入的大小，而不是大小。
Now The regular O(n) case
相比之下，在数组中搜索给定元素的时间是多项式时间：O(n)。它最多需要 n 步，这里 n 是输入的大小（数组的长度）。
[ 看这里 ]
于 2013-10-16T05:50:29.080 回答
2
复杂性基于输入。在背包问题中，输入是大小、最大容量和利润、重量数组。我们将 dp 表构造为size * W，因此我们认为它具有多项式时间复杂度。但是，输入 W 是一个整数，而不是一个数组。因此，它将是 O（大小 *（存储给定 W 所需的位数））。如果没有位增加 1，则运行时间加倍。因此它是指数的，因此是伪多项式的。
于 2021-07-09T13:01:34.577 回答