多重背包的时间复杂度为什么是O(nW∑c[i])

多重背包问题是在给定物品体积、价值和数量的情况下，选择一些物品放入一个容量为W的背包中，使得背包内物品的总价值最大。时间复杂度为O(nW∑c[i])的是一种常见的解法——动态规划。

其中，n表示物品的种类数，W表示背包的容量，c[i]表示第i种物品的数量。对于多重背包问题，我们需要考虑每种物品的数量，因此需要在01背包的基础上再增加一层循环。具体来说，在状态转移方程中，我们需要枚举第i种物品选择的数量k，这样才能得到第i种物品选0个、1个、2个，直至选c[i]个物品的所有情况。而每枚举一次k，就需要更新一次状态，更新状态的时间复杂度为O(W)。因此，总时间复杂度为O(nW∑c[i])。