如果子问题 [0/1 knapsack] 没有重叠，DP 如何提供帮助
How does DP helps if there are no overlapping in sub problems [0/1 knapsack]
针对典型的背包问题考虑以下输入。
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 and https://www.youtube.com/watch?v=ocZMDMZwhCY.
动态规划如何帮助降低此类背包样本的时间复杂度？如果它无助于提高这种情况的时间复杂度，那么 DP 的最坏情况复杂度解决方案也与基于回溯搜索的解决方案相同，即 2 的 n 次方[忽略修剪，就像应用修剪一样，那么解决方案的复杂性将降低，而且 DP 也不会比非记忆递归解决方案更好]
** 上面的示例中是否真的缺少子问题的重叠，或者我遗漏了什么？**
DP 对您的特定问题实例根本没有帮助。但总的来说，即在所有可能的输入实例中，它永远不会比纯递归解决 更多 个子问题，并且在许多情况下它解决的要少得多。 这就是DP很好的原因。
你所有的 DP 公式保证它可以通过解决最多 n(c+1) 个子问题来解决 任何 个问题实例，而且你的例子确实如此：这里 n = 3 和 c = 10，它通过解决 14 <= 33 个子问题（包括原始问题）来解决问题。
类似地，纯递归解决方案保证它可以通过最多解决 2^n 个子问题来解决 任何 个问题实例。
您似乎认为 DP 算法应该比递归算法更快地解决每个问题实例，但事实并非如此，而且没有人提出这种说法。存在没有重叠子问题的实例（如您的实例），对于这些实例，DP 使用与递归解决方案完全相同数量的子问题来解决问题。这并没有说明这两种算法的行为一般。通常，DP 最多使用与递归解决方案一样多的子问题来解决每个问题，有时甚至更少——因为确实存在递归算法需要多次解决相同子问题的问题实例。
简而言之：DP永远不会比递归差，并且在最坏的情况下比递归更好。这确实 不 暗示它在每个实例上都更好。
0/1 背包问题有一个 pseudo-polynomial-time solution。该解决方案的 运行 时间是 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显然是3k显然是7
因此，预测的 运行 时间为 O(k n^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，并且您仍然没有重叠的子问题。
如果权重的 none 加起来与其他权重相加并且容量足够大以包含总重量。
不过，动态规划解决方案是 O(c*n)。这是容量的多项式而不是项目的数量。
在您的示例中 n=3 和 c=10，所以 2^n = 8 和 c*n = 30。这里 c*n 大于 2^n，所以 dp 解决方案没有帮助。如果你有更多的项目和小容量，那么 dp 解决方案会更好。这些是 dp 解决方案可以很好地工作的约束类型。
针对典型的背包问题考虑以下输入。
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 and https://www.youtube.com/watch?v=ocZMDMZwhCY.
动态规划如何帮助降低此类背包样本的时间复杂度？如果它无助于提高这种情况的时间复杂度，那么 DP 的最坏情况复杂度解决方案也与基于回溯搜索的解决方案相同，即 2 的 n 次方[忽略修剪，就像应用修剪一样，那么解决方案的复杂性将降低，而且 DP 也不会比非记忆递归解决方案更好]
** 上面的示例中是否真的缺少子问题的重叠，或者我遗漏了什么？**
DP 对您的特定问题实例根本没有帮助。但总的来说，即在所有可能的输入实例中，它永远不会比纯递归解决 更多 个子问题，并且在许多情况下它解决的要少得多。 这就是DP很好的原因。
你所有的 DP 公式保证它可以通过解决最多 n(c+1) 个子问题来解决 任何 个问题实例，而且你的例子确实如此：这里 n = 3 和 c = 10，它通过解决 14 <= 33 个子问题（包括原始问题）来解决问题。
类似地，纯递归解决方案保证它可以通过最多解决 2^n 个子问题来解决 任何 个问题实例。
您似乎认为 DP 算法应该比递归算法更快地解决每个问题实例，但事实并非如此，而且没有人提出这种说法。存在没有重叠子问题的实例（如您的实例），对于这些实例，DP 使用与递归解决方案完全相同数量的子问题来解决问题。这并没有说明这两种算法的行为一般。通常，DP 最多使用与递归解决方案一样多的子问题来解决每个问题，有时甚至更少——因为确实存在递归算法需要多次解决相同子问题的问题实例。
简而言之：DP永远不会比递归差，并且在最坏的情况下比递归更好。这确实 不 暗示它在每个实例上都更好。
0/1 背包问题有一个 pseudo-polynomial-time solution。该解决方案的 运行 时间是 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显然是3k显然是7
因此，预测的 运行 时间为 O(k n^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，并且您仍然没有重叠的子问题。
如果权重的 none 加起来与其他权重相加并且容量足够大以包含总重量。
不过，动态规划解决方案是 O(c*n)。这是容量的多项式而不是项目的数量。
在您的示例中 n=3 和 c=10，所以 2^n = 8 和 c*n = 30。这里 c*n 大于 2^n，所以 dp 解决方案没有帮助。如果你有更多的项目和小容量，那么 dp 解决方案会更好。这些是 dp 解决方案可以很好地工作的约束类型。