01背包问题时间复杂度

求解01背包问题的时间复杂度取决于所采用的算法。其中，常见的解法有动态规划和暴力解法。

动态规划是解决01背包问题的常用方法，其时间复杂度为O(nC)，其中n为物品的个数，C为背包的容量。这是因为动态规划解法中需要填充一个二维数组，数组的大小为(n+1)×(C+1)。每次填充一个单元格时，需要依赖前一个单元格的值，所以总共需要填充的单元格数为(n+1)×(C+1)，因此时间复杂度为O(nC)。

另一种解法是暴力解法，即对于每一件物品，都有放进背包和不放进背包两种选择。对于n个物品，共有2^n种可能的组合。因此，暴力解法的时间复杂度为O((2^n)×n)。然而，由于计算的数量级过大，暴力解法在实际应用中往往不可行。

综上所述，动态规划解法的时间复杂度为O(nC)，而暴力解法的时间复杂度为O((2^n)×n)。因此，动态规划是求解01背包问题的更优解法。