如果背包容量不足以容纳第一件物品，您只能从之前的物品中进行选择

在前两篇文章中，我们仔细讨论了01背包问题和完全背包问题。在本文中，我们将介绍另一个背包问题-多背包问题。多背包问题的项数介于01背包问题和完全背包问题之间，项数是有限的！

有各种各样的物品和一个背包，容量为。第三项的数量不超过几件。每件物品的体积为，价值为。解决哪些物品装入背包可以使物品的总体积不超过背包的容量，总价值最大。

注：上述字符在本文中的含义相同。

多背包问题与01背包和完整背包的区别在于，01背包只能使用一次，多背包可以使用无数次，而多背包可以多次使用。

01在背包问题中，我们使用二维数组进行计算，这表明当仅使用第一件物品且背包容量为时，我们可以获得最大利润。在这种情况下，通过根据当前背包容量判断物品是否可以装载，我们可以得到以下两个等式：

上面01背包公式的第二项相对简单。如果背包容量不足以容纳第一件物品，您只能从之前的物品中进行选择。让我们仔细分析第一个公式。

如果当前背包容量可以容纳该物品，则我们可以选择该物品或不选择该物品。

[新闻热点]

如果我们不选择第一件物品，我们可以使用有容量的背包来选择第一件。在这种情况下，我们的最大利润是。

如果您选择了该项目，那么我们仍然有背包容量，您可以选择剩余的项目，我们的收入需要增加，因此我们的收入是。

在多个背包的问题中，我们可以使用一件物品的次数多于三次。事实上，我们可以将多个背包转换为01个背包。例如，我们可以将三个项目更改为三个不同的项目。所谓的差异是它们的名称不同，但它们的值和体积相同。假设体积为，值为，可以使用的次数为3，我们可以将它们转换为，，，这三项的体积和值都是，这样，它可以转换为三次，只能使用一次。通过此转换，我们可以将多个背包转换为01个背包。

多背包代码：

与01背包一样，我们也可以使用单列数组优化多个背包：

当背包容量足够时，01背包的动态传递方程为：

上述动态传递方程基于每个项目的选择和非选择。对于多个背包，如果物品可以选择次数，我们可以选择0次，我们可以选1次，…，我们可以选择时间，我们需要选择从这些情况中受益最大的一个，因此，多个背包的动态传递方程如下其中，表示可以选择物品的次数，表示物品的体积，表示当前背包的容量：

基于上述动态传递方程，我们可以获得以下代码：

在本文中，我们主要介绍多背包的两种解决方案。一种是将多个背包转换为01个背包，另一种是根据多个背包的动态传递方程求解问题。可以看出，后者具有较低的空间复杂度并节省更多的内存空间。在下一期中，我们将使用另一种方法优化多个背包。

以上是本文的全部内容。我希望你能得到一些东西。我是乐红。下次见！！！