algorithm - 如何理解降低0~1背包的时间复杂度

Question

对于0~1背包问题，

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

c[i]表示第i件商品的成本，w[i]表示第i种商品的值(value)。

我看了一篇文档，说时间复杂度可以优化，尤其是当V比较大的时候。如下

 i=1...N

 v=V...0 

可以改成

 i=1...n        

bound=max{V-sum{w[i..n]},c[i]}        

 v=V...bound

什么意思？V(包的最大值)怎么减去w[i]( cargo 的值(value))的总和？

真的很困惑，或者这个文档有什么问题吗？

Answer 1

您没有说要优化谁的复杂性。你在使用动态规划吗？如果是这样，这可能意味着您不需要为较小的 v 值计算 f[i][v]，因为您不需要这些值来找到最优值。

即使你把从i + 1到n的所有元素都放在背包里，你的容量还是V - sum{c[i+ 1..n]} 剩余，所以不需要解决容量较小的子问题i(仅限于商品1..i)

如果您需要更正式的答案，请详细描述问题以及所使用的算法。