如果子问题没有重叠，那么DP如何帮助解决0/1背包问题？

Question

考虑典型背包问题的以下输入。

V = [10,8,12]
W = [2,3,7]
i =  1,2,3
C = 10

我尝试使用带记忆化的递归来解决这个示例，但没有发现重叠子问题。

递归过程的签名：

knapsack(int c, int i) 

最初被称为knapsack(10,1)

解决方案的方法就像在https://www.youtube.com/watch?v=6h6Fi6AQiRM和https://www.youtube.com/watch?v=ocZMDMZwhCY中所解释的那样。

动态规划如何帮助减少此类背包问题的时间复杂度？如果它不能帮助改善此案例的时间复杂度，那么DP解决方案的最坏情况复杂度是否与基于回溯搜索的复杂度相同，即2的n次方[忽略修剪，因为如果应用修剪，则复杂度将减少，并且再次DP不会比非记忆递归解决方案更好]

** 在上面的示例中，子问题之间是否真的缺少重叠部分，还是我错过了什么？**

- nits.kk

---

背包问题被认为是NP完全或NP难的，具体取决于其准确的表述方式，因此找到一个没有指数运行时间的算法将会非常令人惊讶。 - Daniel Wagner

DP是一般术语，指允许在多项式时间内解决指数问题的技术。记忆化是DP中使用的一种技术，但并不是用于0/1背包问题的技术。 - user3386109

这里是0/1背包问题的解决方案：https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem - user3386109

@user3386109，感谢您的回答，我看了维基链接，也早就看过这个解决方案。但正如我在问题中提到的视频链接中的教授所说，使用记忆化递归只是解决问题的另一种视角，如果我们希望使用涉及表格的自底向上方法或者使用记忆化递归，这并不重要。 - nits.kk

对于动态规划，必须具备重叠子问题，但我在我的样本中找不到它。如果您能帮助我为上述样本定义它，那将对我很有帮助。 - nits.kk

Answer 1

DP 在你的具体问题实例中并没有提供帮助。但是一般而言，即在所有可能的输入实例中，它从未解决比纯递归更多的子问题，并且在许多实例上解决的子问题要少得多。这就是 DP 好的原因。

你所有的 DP 公式所保证的是，通过解决最多 n(c+1) 个子问题，它可以解决任何问题实例，对于你的示例确实如此：这里 n=3，c=10，它通过解决14<=33个子问题（包括原始问题）来解决该问题。

同样地，纯递归解决方案保证可以通过解决最多 2^n 的子问题来解决任何问题实例。

你似乎认为 DP 算法应该比递归算法更快地解决每个问题实例，但这不是真的，也没有人声称过这一点。存在一些问题实例（如你的问题），其中不存在重叠的子问题，对于这些实例，DP 使用与递归解决方案完全相同数量的子问题来解决问题。这并不说明两种算法总体上的行为。总体而言，DP 解决每个问题时所需的子问题最多与递归解决方案相同，并且有时比递归更少——因为确实存在问题实例需要递归算法多次解决相同的子问题。

简而言之：DP 永远不会比递归更差，在最坏情况下比递归更好。这并不是意味着它在每个实例上都更好。

- j_random_hacker

---

回答得非常到位。完美，这就是问题中所问的。 - codemania23

Answer 2

0/1背包问题有一个伪多项式时间的解决方案。该解决方案的运行时间为O(nW)，其中n是可供选择的物品数量，W是背包可以容纳的重量。运行时间被描述为伪多项式，因为W不是n的函数。

或者说它是吗？给定一个由重量和价值组成的n个项目列表，存在一个项目的最大重量，称之为k。（这个最大重量可以在O(n)的时间内确定。）如果W大于或等于kn，则问题是微不足道的，所有物品都适合于背包中。因此，我们只需要考虑W < kn的情况。因此，为了进行复杂度分析，W可以表示为n的函数。

考虑到 nW <= k n^2，该算法的运行时间为 O(k n^2)。

现在，听众中的学究会争辩（正确地），这仍然是伪多项式时间，因为 k 和 n 之间没有定义的关系。但是问题的任何具体陈述（按重量和价值列出项目）必须在问题陈述本身中明确指定 k 的常数值。

够了理论。我们如何将其应用于问题中的示例。

• n 明显为 3
• k 明显为 7

因此，预测的运行时间为 O(k n^2) = O(7x3x3) = 63。但是预测的指数运行时间（没有 DP）为 O(2^n) = O(2^3) = 8。

这里有你所举的例子存在的问题。大 O 分析描述了算法在大量 n 值下的渐进行为。它对于小值的 n 的性能几乎没有任何作用。如果 n 的值足够小，使得 2^n < k n^2，那么就没有期望动态规划会提高算法的运行时间，或者根本不会产生任何影响。

你的挑战是找到一个例子，其中 2^n > k n^2，但仍然没有重叠子问题。

- user3386109

Answer 3

一种具有记忆化的递归解决方案如果没有任何权重相加等于其他权重并且容量足够包括总重量，则其运行时间可接近2^n。

动态规划的解决方案将是O(c*n)。这在容量方面是多项式的，而不是物品数量。

在您的示例中，n=3且c=10，因此2^n = 8且c*n = 30。在这里，c*n大于2^n，因此dp解决方案无法提供帮助。如果您有更多的物品和较小的容量，则dp解决方案将更好。这些是dp解决方案可以很好地处理的约束条件。

- fgb

Answer 4

@nits.kk

这里有一个包含5个元素{1, 2, 3, 4, 5}，C = 36的例子

总子问题数=31

重叠问题=12

唯一子问题=19

重叠问题重复计数：

1. 容量=33，重量：[4, 5]，计数=2
2. 容量=33，重量：[5]，计数=2
3. 容量=32，重量：[5]，计数=2
4. 容量=31，重量：[5]，计数=2
5. 容量=30，重量：[5]，计数=2
6. 容量=29，重量：[5]，计数=2

---

显然，我无法为10个元素生成图像。但是，如果您运行元素为{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} C = 121的问题，则以下是统计信息：

总子问题数=1023

重叠问题=974

唯一子问题=49

我希望这使得重叠子问题变得清晰明了。

- apatniv