algorithm - 如果子问题 [0/1 knapsack] 没有重叠，DP 如何提供帮助

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 也不会比非内存递归解决方案更好]

** 上面的示例中是否真的缺少子问题的重叠，或者我遗漏了什么？**

Answer 1

DP 对您的特定问题实例完全没有帮助。但总的来说，即在所有可能的输入实例中，它永远不会解决比纯递归更多的子问题，而且在许多情况下它解决的要少得多。 这就是 DP 很好的原因。

所有你的 DP 公式保证它可以通过解决最多 n(c+1) 个子问题来解决问题的任何实例，事实上它这样做是为了您的示例:此处 n = 3 和 c = 10，它通过解决 14 <= 33 个子问题(包括原始问题)来解决问题。

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

您似乎认为 DP 算法应该比递归算法更快地解决每个问题实例，但事实并非如此，而且没有人提出这种说法。存在没有重叠子问题的实例(如您的实例)，对于这些实例，DP 使用与递归解决方案完全相同数量的子问题来解决问题。这并没有说明这两种算法的行为一般。一般而言，DP 最多使用与递归解决方案一样多的子问题来解决每个问题，有时甚至更少——因为确实存在递归算法需要多次解决相同子问题的问题实例。

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