如果子问题没有重叠,DP如何帮助[0/1背包]

Question

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

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

我尝试使用memoization进行递归来解决此示例但发现没有重叠的子问题.

递归程序的签名:

knapsack(int c, int i) 

最初称为 knapsack(10,1)

解决方案的方法类似于https://www.youtube.com/watch?v=6h6Fi6AQiRM和https://www.youtube.com/watch?v=ocZMDMZwhCY中所述.

动态编程如何帮助减少这些Knapsack样本的时间复杂度？如果它没有帮助改善这种情况的时间复杂度,那么DP解决方案的最坏情况复杂性也与基于后向跟踪搜索相同,即2到功率n [ 忽略修剪,就像修剪应用那样复杂性将降低两者解决方案再次DP将不会比非memoized递归解决方案更好 ]

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

Answer 1

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

你所有的DP配方保证是它可以通过解决大多数子问题来解决问题的任何实例n(c+1),事实上它也适用于你的例子:here n= 3和c= 10,它通过解决14 <= 33个子问题解决了这个问题(包括原始问题).

类似地,纯粹的递归解决方案保证它可以通过解决最多的子问题来解决问题的任何实例2^n.

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

简而言之:DP永远不会比递归更糟糕,并且比最坏情况下的递归更好.但这并不意味着它是在所有实例更好.

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(kn ^ 2).

现在,观众中的学生将(正确地)认为这仍然是伪多项式时间,因为在k和之间没有确定的关系n.但是问题的任何具体陈述(按权重和值列出项目)必须k在问题陈述本身中具有明确的常量值.

足够的理论.我们如何将此应用于问题中的示例.

• n 显然是3
• k 显然是7

因此,预测的运行时间是O(kn ^ 2) = O(7x3x3) = 63.但是预测的指数运行时间(没有DP)是O(2 ^ n) = O(2 ^ 3) = 8.

你的例子就有问题了.Big-O分析描述了大值的算法的渐近行为n.它告诉你几乎没有关于小值的性能n.如果值n足够小2^n < k n^2,则不会期望DP会改善算法的运行时间,或者根本没有任何影响.

您的挑战是找到一个示例2^n > k n^2,并且您仍然没有重叠的子问题.