使用DP算法降低背包0〜1的时间复杂度 [英] Reducing time complexity of Knapsack 0~1 while using DP algorithm

问题描述

我正在使用DP算法，即在一个轴上的2D数组中存储子问题值

I'm using DP algorithm, i.e. storing sub-problem values in 2D array where one axis

表示 n 项和其他- w 值从 0 到 W 其中 W 是最大的背包容量

means n items and other - w values from 0 to W where W is the maximum

背包容量。因此， T [n-1] [W] 值是我需要

capacity of knapsack. Therefore T[n-1][W] value is the optimum I need to

计算的最佳值。我在其他消息来源中读过，该算法的时间复杂度为

calculate. I've read in other sources that time complexity of this algorithm is

O（nW）。我的问题是：是否可以进一步降低时间复杂度？

O(nW). My quesiton would be: is it possible to reduce this time complexity even more?

我找到了另一个回答，几乎都在讨论同样的事情，但是如果没有它我就不能低估它示例：如何了解如何降低0的时间复杂度1个背包

I found other answer which talks about pretty much same thing but I can't understant it without example: how to understand about reducing time complexity on 0~1 knapsack

我告诉我们不需要计算 T [i] [w] w 的较小值，因为它们未在最佳状态下使用，但我无法正确地获得此值，有人可以给出详细而直观的示例吗？

I tells that we de not need to to calculate T[i][w] with small w values as they are not used in the optimum, but I can't get this properly, could anyone give detailed and visual example? This would benefit me a lot.

推荐答案

您要填充的2D数组的大小为 n 乘 W （实际上是W + 1，因为值从 0..W ，但在此不影响渐近复杂性）。因此，要填充该数组，您至少需要完成 n * W 工作（即使您只是将数组初始化为全零！）。

The 2D array you're trying to fill is of size n by W (actually, W+1 since the values go from 0..W, but off-by-one doesn't affect the asymptotic complexity here). Therefore, to fill that array, you would need to do at least n*W work (even if you just initialize the array to all zeroes!).

因此，就渐近算法时间复杂度而言，Θ（nW）（紧密约束，分别为O（nW）和Ω（nW））是最好的。

Therefore, Θ(nW) (tightly bound, which is both O(nW) and Ω(nW)) is the best you can do in terms of asymptotic algorithmic time complexity.

这就是使动态编程解决方案如此酷的原因，在于您需要在解决方案数组的每个元素（在本例中为2D）上花费恒定的时间，从自底向上（将其与自上而下的递归解决方案的复杂性进行对比！）。

This is what makes the dynamic programming solution so cool, is that you spend constant time on each element of the solution array (in this case, 2D) doing some constant work, from the bottom up (contrast this to the complexity of the top-down recursive solution!).

这篇关于使用DP算法降低背包0〜1的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！