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 个商品的价值。

我读了一个文档，它说时间复杂度可以优化，特别是当 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]（商品价值）的总和？

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

Answer 1

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

即使你把所有的货物从i + 1到n到背包里，你仍然有一个V - sum{c[i+1..n]}剩余的容量，所以你不需要解决容量小于那个的子问题i（限制为货物）。1..i

如果您需要更正式的答案，请描述问题以及正在使用的算法，并提供更多详细信息。