使用DP算法降低Knapsack 0~1的时间复杂度
Reducing time complexity of Knapsack 0~1 while using DP algorithm
我正在使用 DP 算法，即将子问题值存储在二维数组中，其中一个轴
表示 n 项和其他 - w 从 0 到 W 的值，其中 W 是最大值
背包容量。因此 T[n-1][W] 值是我需要的最佳值
计算。我在其他来源读到这个算法的时间复杂度是
O(nW)。我的问题是：是否可以进一步降低时间复杂度？
我找到了其他答案，其中谈到了几乎相同的事情，但没有例子我无法理解它：how to understand about reducing time complexity on 0~1 knapsack
我说我们不需要用小的 w 值来计算 T[i][w] 因为它们没有在最优中使用，但是我不能正确地得到这个，谁能给出详细的和视觉示例？这会让我受益匪浅。
您要填充的二维数组的大小为 n 乘以 W（实际上，W+1，因为值来自 0..W，但不符合-一个不影响这里的渐近复杂性）。因此，要填充该数组，您至少需要做 n*W 工作（即使您只是将数组初始化为全零！）。
因此，Θ(nW)（紧密结合，既是 O(nW) 又是 Ω(nW)）是您在渐近算法时间复杂度方面所能做的最好的。
这就是动态规划解决方案如此酷的原因，因为您在解决方案数组（在本例中为 2D）的每个元素上花费恒定的时间，自下而上地做一些恒定的工作（将此与自上而下的递归解决方案的复杂性！）。
我正在使用 DP 算法，即将子问题值存储在二维数组中，其中一个轴
表示 n 项和其他 - w 从 0 到 W 的值，其中 W 是最大值
背包容量。因此 T[n-1][W] 值是我需要的最佳值
计算。我在其他来源读到这个算法的时间复杂度是
O(nW)。我的问题是：是否可以进一步降低时间复杂度？
我找到了其他答案，其中谈到了几乎相同的事情，但没有例子我无法理解它：how to understand about reducing time complexity on 0~1 knapsack
我说我们不需要用小的 w 值来计算 T[i][w] 因为它们没有在最优中使用，但是我不能正确地得到这个，谁能给出详细的和视觉示例？这会让我受益匪浅。
您要填充的二维数组的大小为 n 乘以 W（实际上，W+1，因为值来自 0..W，但不符合-一个不影响这里的渐近复杂性）。因此，要填充该数组，您至少需要做 n*W 工作（即使您只是将数组初始化为全零！）。
因此，Θ(nW)（紧密结合，既是 O(nW) 又是 Ω(nW)）是您在渐近算法时间复杂度方面所能做的最好的。
这就是动态规划解决方案如此酷的原因，因为您在解决方案数组（在本例中为 2D）的每个元素上花费恒定的时间，自下而上地做一些恒定的工作（将此与自上而下的递归解决方案的复杂性！）。