如何降低0〜1背包的时间复杂度 [英] how to understand about reducing time complexity on 0~1 knapsack

问题描述

关于0〜1背包问题，

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

c [i]表示第i种商品的成本， w [i]表示第i种商品的价值.

c[i] means the cost of ith goods, w[i] means the value of ith goods.

我读了一个文档，说时间复杂度可以优化，尤其是当V较大时.如下所示

And I read one doc,which said the time complexity can be optimization,especially when V is larger.as below

 i=1...N

 v=V...0 

可以更改为

 i=1...n        

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

 v=V...bound

是什么意思?V(袋的最大值)减去w [i](商品的价值)之和?

what does it mean?How can V(the maximum of bag) minus sum of w[i](the value of goods)?

真的混淆了，还是这个文档有问题?

Really confuse,or something wrong on this doc?

推荐答案

您没有说要优化的复杂性.您正在使用动态编程吗?如果是这样，这可能意味着您不需要为v的较小值计算f[i][v]，因为您不需要这些值即可找到最佳值.

You didn't say whose complexity you are optimizing. Are you using dynamic programming? If so, this could mean that you don't need to calculate f[i][v] for small values of v, because you won't need those values to find the optimum.

即使将所有从i + 1到n的商品放在背包中，也仍然有V - sum{c[i+1..n]}的容量，因此您无需解决子问题i(限于商品1..i)的容量小于该容量.

Even if you put all goods from i + 1 to n in the knapsack, you still have a capacity of V - sum{c[i+1..n]} left, so you don't need to solve the subproblem i (restricted to goods 1..i) with a capacity smaller than that.

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

If you need a more formal answer, please describe the problem, as well as the algorithm being used, with more details.

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