讲解一下多重背包

多重背包是背包问题的一种扩展形式。在多重背包问题中，每种物品的数量不再是只有一个，而是有多个可供选择。

具体来说，多重背包问题给定了n种物品和一个背包，物品i的重量为wi，价值为vi，数量为mi。背包的容量为W。要求选择物品放入背包中，使得背包的总重量不超过容量限制，并且背包中物品的总价值最大。

多重背包问题可以使用动态规划来解决。定义一个二维数组dp，其中dp[i][j]表示前i种物品放入容量为j的背包中所能获得的最大价值。

首先，初始化dp数组的第一行和第一列为0，表示背包容量为0或者物品种类为0时，背包中的物品价值都为0。

然后，从第一种物品开始，依次计算dp数组中的每个值。对于第i种物品，需要遍历背包容量从0到W，计算出每个容量下的最大价值。

在计算dp[i][j]时，可以分为两种情况：

1. 如果第i种物品的数量mi大于j/wi（即背包容量除以物品重量），则只能选择mi个物品放入背包，此时背包的价值为mi * vi，即dp[i][j] = mi * vi。
2. 如果第i种物品的数量mi小于等于j/wi，那么可以选择放入0个、1个、2个......mi个物品到背包中，计算出每种情况下的最大价值，取其中的最大值作为dp[i][j]的值。即dp[i][j] = max(dp[i-1][j-kwi] + kvi)，其中0 <= k <= min(mi, j/wi)。

最后，dp[n][W]即为所求的最大价值，表示前n种物品放入容量为W的背包中所能获得的最大价值。

多重背包问题的时间复杂度为O(nWsum(mi))，其中n为物品种类数，W为背包容量，sum(mi)为物品数量的总和